[Data Structure] 힙 정렬(heap sort)

---

힙 정렬

 

 

최소 힙이나 최대 힙을 이용하는 정렬 방법이다. 최소 힙이나 최대 힙에 삽입한 후에 루트노드부터 삭제하면서 추출하면 정렬이 된다.

힙을 구현하는 것이 귀찮을 뿐 힙이 구현되어 있다면 간편하게 구현할 수 있는 정렬 방법이고, 시간복잡도도 삽입에서 $ \mathcal{O}(\log_2 n) $, 삭제에서 $ \mathcal{O} (\log_2 n) $ 인데, 각 원소마다 삽입 삭제가 일어나므로 $ \mathcal{O} (n \log_2 n) $ 의 시간복잡도를 가지기 때문에 준수한 정렬 방법이다.

힙과 관련된 내용은 링크를 참고하면 된다.

 

---

구현 | C

 

void heap_sort(int list[], int n) {
    Heap heap;
    init(&heap);
    for (int i = 0; i < n; i++) {
        insert(&heap, list[i]);
    }
    for (int i = n - 1; i >= 0; i--) {
        list[i] = delete(&heap);
    }
}