[COSE214[] Heap Sort

Max Heap의 조건과 구조에 대해 서술하시오.

 

Max heap이 되기 위해서는 먼저 1) heap의 shape이 binary tree의 무조건 앞쪽에서부터 순서대로 노드를 채우는 almost complete binary tree 형태여야 한다. 2) 그리고 항상 위쪽 node가 아래쪽 node보다 큰 max heap property를 갖추어야 한다. 

이렇게 형성된 almost CBT의 index로는 특정 node의 번호가 i라고 할 때 parent node는 i/2, left node는 2i, right node는 2i+1이라는 index를 가진다.  또한 height of a node는 leaf에서 0이고, upwards로 가며 숫자가 커진다. depth of a node의 경우 root에서 0이고, downwards로 가며 숫자가 커진다.

Max-heapify, Build-max-heap, Heapsort

Max-heapify란 부분적으로는 max heap 형태를 가지지만 전체적으로는 Max heap이 아닌 구조를 max heap으로 만들어주는 과정을 말한다. 특정 노드를 기준으로 자식 노드와 비교하여 필요한 경우 위치를 교환하고, 교환된 자식 노드를 기준으로 다시 max-heapify를 수행하는 재귀적인 과정이다. 

Build-max heap은 주어진 배열을 max heap으로 구성하는 과정이다. 

heapsort는 정렬 알고리즘으로, 먼저 주어진 배열을 build-max-heap을 통해 maxheap으로 구성한다. 이 때 maxheap의 root node는 항상 배열에서 가장 큰 값이므로 root node를 배열의 마지막 요소와 교환한 후, 배열의 크기를 하나 줄인다. 그 후 변경된 root node에 대해 다시 max-heapify를 수행하여 maxheap 구조를 유지시킨다. 이 과정을 배열의 크기가 1이 될 때까지 반복하여 정렬된 배열을 얻어내는 방식이다. 

이 때 build-maxheap의 시간 복잡도는 O(n)이고, max-heapify의 시간복잡도는 O(lg n)인데 heapsort의 경우 두 과정이 반복되며 이루어지기 때문에 시간복잡도는 O(nlgn)이 된다.