Heap Sort(힙 정렬)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

Heap Sort(힙 정렬)

힙 정렬이란 최대 힙이나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.

1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.

2. 최대 힙을 구성한다. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 

단말 노드를 자노드로 가진 부노드로부터 구성하며 아래 부터 루트까지 올라오며 순차적으로 만들어갈 수 있다.

3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.

4. 2와 3을 반복한다.

Heap의 정의

Heap은 Complete Binary Tree이면서 Heap Property를 만족해야 한다.

Complete Binary Tree란 아래 그림과 같이 마지막 레벨을 제외하면 완전히 꽉 차있고, 마지막 레벨에는 가장 오른쪽부터 연속된 몇개의 노드가 비어있을 수 있는 tree

 

Heap Property란 Max Heap Property, Min Heap Property로 나뉘어 진다.

Max Heap Property란 부모는 자식보다 크거나 같다.

반대로 Min Heap Property란 부모는 자식보다 작거나 같다.

힙은 일차원 배열로 표현 가능하다. : A[1...n]

- 루트 노드 A[1]

- A[i]의 부모 = A[i/2]

- A[i]의 왼쪽 자식 = A[2i]

- A[i]의 오른쪽 자식 = A[2i + 1]

위의 내용을 바탕으로 배열 [2, 8, 6, 1, 10, 15, 3, 12, 11]을 힙으로 만드는 과정

[2, 8, 6, 1, 10, 15, 3, 12, 11]

[2, 8, 6, 12, 10, 15, 3, 1, 11]

[2, 8, 15, 12, 10, 6, 3, 1, 11]

[2, 12, 15, 8, 10, 6, 3, 1, 11]

[2, 12, 15, 11, 10, 6, 3, 1, 8]

[15, 12, 2, 11, 10, 6, 3, 1, 8]

[15, 12, 6, 11, 10, 2, 3, 1, 8]

MAX-HEAPIFY 의사코드

MAX-HEAPIFY(A, i) {
if there is no child of A[i]
return;
k <- index of the biggest child of i;
if(A[i] >= A[k])
return;
exchange A[i] and A[k];
MAX-HEAPIFY(A, k);
}

root 노드에 대한 HEAPIFY는 MAX-HEAPIFY(1)를 호출하면 됨.

MAX-HEAPIFY 의사코드를 기반으로 반복문으로 변경

MAX-HEAPIFY(A, i) {
while A[i] has a child do
k <- index of the biggest child of i;
if A[i] >= A[k]
return;
exchange A[i] and A[k];
i = k;
end.
}

시간복잡도

힙의 시간복잡성은 이다. 왜냐하면 이진트리의 속성 에서,  이므로 힙트리의 높이가 이 됨을 알 수 있다.

소스 코드(Java)