힙 정렬

힙 정렬(Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성해야 하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.

1. n개의 노드에 대한 전이진 트리를 구성. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.
2. 최대 힙을 구성. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드부터 구성하며 아래부터 루트까지 순차적으로 만들어 갈 수 있다. 단, 트리의 특성상 인덱스는 1부터 사용한다(0에 2를 곱해도 계속 0이 되는 현상을 방지)
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환.
4. 2와 3을 반복한다.

이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어 지므로 O(n)의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체시간은 힙 구성시간과 n개의 데이터 삭제 및 재구성 시간을 포함한다. 시간 복잡도는

              = (log n+log(n-1)+...+log 2) 
            = (log n+log(n-1)+...+log 2)+(log n+log(n-1)+...+log 2)
            = O(n*log n)

따라서 힙 정렬은 일반적인 경우 $O(n \log n)$의 시간복잡도를 가진다.