[알고리즘] 힙정렬(Heap sort)이란?

1.힙정렬이란?

Heap sort

힙정렬(Heap sort)이란, 힙이라는 자료구조를 이용하여 정렬을 하는 방법이다. 합병 정렬(Merge sort)이나 퀵 정렬(Quick sort)만큼 빠른 정렬 알고리즘 중 하나이다. 
여기서 말하는 힙은 자료구조 중 하나로 마지막 레벨을 제외한 모든 레벨이 완전히 채워져야 하는 완전 이진 트리라는 특성과, 힙의 부모 노드가 항상 자식 노드보다 크거나 작은 값을 가지는 힙 속성(heap property)이라는 특성 두 가지를 가지고 있다. 이 때 힙 속성에 대해서 조금 더 설명을 해 보자면 부모 노드가 자식 노드보다 항상 큰 경우를 max-heap이라고 하고 그 반대로 항상 작은 경우를 min-heap이라고 한다. 

완전 이진 트리는 위 사진과 같이 트리의 마지막 레벨을 제외한 모든 속성이 완전히 채워져 있는 경우를 말한다. 또한 이 경우에 마지막 레벨은 왼쪽에서부터 채워져 있어야 완전 이진 트리의 성질을 만족한다. 예를들어 추가적으로 3이라는 노드에 자식 노드가 하나 있다고 가정하면, 왼쪽에서부터 채워지지 않았으므로 완전 이진 트리가 아니게 된다. 

또한 위 사진은 부모 노드가 자식 노드들보다 크게 정렬이 되어 있으므로 max-heap의 속성을 가진다고 말할 수 있다. 

 

이러한 힙 자료구조를 이용하여 오름차순으로 힙정렬을 하는 순서는 다음과 같다. 

1. 주어진 배열을 최대 힙(max heap)으로 구성한다. 이를 위해서는 배열을 힙 속성을 만족하는 형태로 재구성하는 Heapify라는 작업을 통해 주어진 배열을 순회하면서 부모 노드와 자식 노드를 비교하여 필요한 경우 위치를 교환해가면서 최대 힙을 만든다.
2. 최대 힙에서 루트 노드에 있는 가장 큰 값을 꺼내어 배열의 마지막 요소와 교환한다.
3. 그리고 마지막으로 간 그 큰 값을 제거한다. 
4. 제일 큰 값과 마지막에 있던 값을 바꾸었으므로, 최대 힙으로 구성하려는 속성이 깨졌을 수 있다. Heapify를 수행하여 다시 최대 힙을 구성할 수 있도록 한다. 
5. 반복하여 정렬되지 않은 부분 배열의 크기가 1이 될 때까지 2~4번을 반복한다. 

2.힙정렬의 예시

array A = {4,1,3,2,16,9,10,14,8,7}을 오름차순으로 정렬한다고 생각해보자.

일단 주어진 배열을 오른쪽과 같이 완전 이진 트리 형태로 만들어준다. 이렇게 완전 이진트리로만 만든 직후에는 max-heap 또는 min-heap이라는 속성을 만족하지 못하고 있는 상태이기 때문에, 원하는 정렬 순서에 따라서 max 또는 min heapify를 해준다. 우리는 오름차순으로 정렬할 예정이기 때문에 max heapify를 실시한다. 

왼쪽의 그림처럼 부모노드가 자식노드보다 무조건 큰 max-heap의 속성을 만족하게 되었으면, 제일 위에 있는 루트 노드인 16과 맨 마지막에 위치한 1과의 자리를 바꾸고, 16은 삭제한다. 바이너리 트리에서 없어지기 때문에 삭제라고 표현하지만, 실제로는 결과 배열에 추가하는 것이라고 생각하면 된다. 

3.힙정렬의 pseudo code

BUILD-MAX-HEAP(A)
for i = A.length downto 2
	exchange A[1] with A[i]
	A.heap-size= A.heap-size-1
	MAX-HEAPIFY(A, 1)

4.공간복잡도

힙정렬은 추가적인 공간을 필요로 하지 않는 in-place알고리즘이기 때문에 데이터 만큼만의 공간이 필요하기 때문에 O(n)의 공간 복잡도를 가지고 있다.

5.시간복잡도

힙정렬의 경우, best case, average case, worst case 모두 동일하게 O(nlogn)의 시간 복잡도를 가지고 있다. 힙을 구성하는 Heapify 과정에서 log n의 시간 복잡도가 소요되며, 이 과정을 n번 수행해야 하기 때문이다. 최상이나 최악의 경우에도 동일한 연산을 수행해야 하기 때문에 어떤 케이스인지에 상관 없이 동일한 시간 복잡도를 보인다는 특징이 있다.