힙 정렬(Heap Sort)

최대 힙 트리나 최소 힙 트리를 구현해 정렬하는 방법이다.

트리 구조로 보여주는 움짤을 찾아보려 했으나 귀찮았다.

n개의 노드에 대해 완전 이진 트리를 구성한다.
heapify과정을 통해 부모노드의 요소가 자식노드의 요소보다 크도록 만든다.
가장 첫번째 요소와 가장 마지막 요소를 swap후 다시 heapify한다.

#include <iostream>
using namespace std;

int heap[10] = {10,5,4,6,2,3,7,9,1,8};

int main() {
	for(int i = 1; i < 10; i++)	{
		int c = i;
		do {
			int root = (c - 1) / 2;
			if(heap[root] < heap[c]) {
				int temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
			c = root;
		} while(c != 0);
	}
	for(int i = 9; i >= 0; i--) {
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int c = 1;
		do {
			c = 2 * root + 1;
			if(heap[c] < heap[c + 1] && c < i - 1) {
				c++;
			}
			if(heap[root] < heap[c] && c < i) {
				int temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
			root = c;
		} while(c < i);
	}
	for(int i = 0; i < 10; i++)
		cout << heap[i] << " ";
}

위 코드는 최대 힙 트리를 통해 정렬한다.

최대 힙 트리는 부모노드의 요소가 자식노드의 요소보다 크다.

추가적인 메모리를 필요로 하지 않으면서 모든 경우에 대해 O(NlogN)의 시간복잡도를 보장받는다.
만능처럼 보이지만 실제로는 퀵소트가 더 빠르고 데이터의 상태에 따른 편차가 발생한다. 또 stable을 보장받지 못한다.

heapify과정은 트리의 깊이 만큼 진행되므로 logN 만큼 수행하고 swap하는 과정을 n번 하면 정렬되므로 O(NlogN)의 시간복잡도가 나온다.

algorithm	average	worst	best	space
heap	O(NlogN)	O(NlogN)	O(NlogN)	O(1)