힙정렬(Heap Sort)

힙정렬(Heap Sort)은 힙(Heap)이라는 특수한 자료구조를 사용하는 정렬 알고리즘이다. 힙은 최소힙(Minimum Heap)과 최대힙(Maximum Heap)이 있는데 값이 저장되는 방향만 반대일 뿐 성질은 똑같다.

우선 힙(heap)에 대해서 설명하면, 힙은 이진트리(Binary Tree)로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있다(nearly complete binary tree). 힙은 최소힙, 최대힙에 따라 다음의 성질을 가지고 있다.

최소힙(minimum heap)의 성질

• 각 노드의 값은 자신의 자식의 값보다 작다.

최대힙(maximum heap)의 성질

• 각 노드의 값은 자신의 자식의 값보다 크다.

위의 그림은 최대힙(maximum heap)의 예를 나타낸다. (a)는 최대힙의 성질을 만족하는 힙이다. (b)의 경우는 nearly complete binary tree는 만족하나 최대힙의 성질을 만족하지 않아 힙이 될수 없다. (c)는 nearly complete binary tree를 만족하지 않으므로 힙이 될 수 없다.

힙은 동일한 데이터를 가져도 각 원소들이 다른 위치에 존재할 수도 있다. 다음의 예가 이를 나타낸다.

힙을 나타내기 위한 자료구조로 링크드리스트나 포인터 같은 것을 써서 표현할 수 도 있으나 꽉 찬 이진트리의 성질(nearly complete binary tree)의 성질을 가지기 때문에 쉽게 일차원의 배열로 표현이 가능하다.

위 예제에서 배열의 첫번째 원소 A[1]부터 끝 원소인 A[6]까지를 힙으로 나타낸 것이다. 차례대로 1~6까지 번호를 메기며 나타내면 된다. 그러면 힙의 루트노드는 A[1]이 된다. 그러면 A[i]째 노드의 부모노드는 A[i/2]이게 되고 A[i]의 왼쪽 자식은 A[2i], 오른쪽 자식은 A[2i+1]이 된다.

배열을 최대힙으로 만드는 과정을 살펴보자. 어떤 노드 x을 루트로 삼고 왼쪽 부트리와 오른쪽 부트리는 힙을 만족한다고 가정하자. 즉, 유일하게 루트만이 힙성질을 만족안한다고 가정하자. 이를 힙의 성질을 만족시키게(Heapify) 하는 예는 다음과 같다.

여기서 루트 노드인 6의 왼쪽,오른쪽 부트리는 힙의 성질을 만족하고 루트 노드인 6만 자신의 자리를 찾아 이동하면 된다.

위의 그림에서 루트인 4가 최대힙(maximum heap)을 만족하기 위해 자신의 자리를 찾아가는 과정이다. 우선 4의 왼쪽,오른쪽 자식 중 더 큰 수와 비교하여 자리를 바꾼다. 그러면 16이 올라가고 그 자리에 4가 내려가게 된다. 또다시 4의 왼쪽, 오른쪽 자식 중 더 큰수와 비교하여 자리를 바꾸면 8이 올라고오고 그 자리에 4가 내려가게 된다. 이를 한번 더 수행하여 5가 올라오게 되고 4가 그 자리로 내려가게되면 최대힙이 만들어지게 된다.

최대힙을 만드는 슈도코드는 다음과 같다.

이를 좀더 구체적으로 기술한 슈도코드는 다음과 같다.

지금까지 루트 x의 왼쪽, 오른쪽 부트리가 힙의 성질을 만족할 때 루트 x의 자리를 이동시켜 힙을 만족시키는 MAX-HEAPIFY를 살펴보았다. 이를 이용해 주어진 입력 배열 전체를 힙으로 만드는 과정을 살펴볼 것이다. 이는 위에서 작성한 MAX-HEAPIFY() 함수를 이용하면 되는데 배열의 제일 끝에서 부터 처음까지 MAX-HEAPIFY를 시키면서 올라가면 배열 전체가 힙이 된다. 즉, 배열의 힙구조로 나타내면 제일 밑인 리프노드부터 하나씩 MAX-HEAPIFY()를 호출하여 루트까지 이동하면 전체가 힙이 된다. 이렇게 진행하면 i를 제외한 왼쪽, 오른쪽 부트리가 힙이 되므로 정상적으로 MAX-HEAPIFY()가 수행이 된다.

하지만 여기서 알아야할 것은 굳이 제일 리프노드 부터 올라갈 필요가 없다는 것이다. 인덱스 i의 자식이 없는 경우에는 heapify를 시킬 필요가 없으므로 자식을 가지는 노드들 중에서 끝 인덱스 부터 루트까지 올라가면 된다. 배열이 A[1, 2, ... , n]이라고 할때 A[n/2]가 자식을 가지는 노드들 중 가장 끝이다. 이유는 위에서 노드 A[i]의 부모노드는 A[i/2]라고 하였으니 배열의 제일 끝으로 하는 노드의 부모는 A[n/2] 이기 때문이다.

이를 슈도코드를 나타내면 다음과 같다.

입력 받은 배열을 heapify 시키는 예는 다음과 같다.

이제 입력받은 배열이 힙이 되는데 아직 배열에 완벽히 정렬이 된 것은 아니다. 위 예제에서 (f)가 최종적인 힙인데 배열로 나타내면 {16, 14 , 10, 8, 7, 9, 3, 2, 4, 1} 이므로 정렬이 된 것이 아니다. 따라서 몇가지의 작업을 수행해야된다. 그 수행은 다음과 같다.

1. 주어진 데이터(배열)로 힙을 만든다.
2. 힙에서 최대값(루트)을 가장 마지막 값과 바꾼다.
3. 힙의 크기를 1 줄어든 것으로 간주한다.
4. 루트노드에 대해서 HEAPIFY()한다.
5. 2~4번을 반복한다.

이에 대한 예제는 다음과 같다.

이를 수행하게 되면 배열이 이제 정렬이 완료되게 된다. 이를 슈도코드로 나타낸 것은 다음과 같다.

힙정렬(Heap Sort)의 시간복잡도를 계산하면 O(nlogn)이다.