33. Heap Sort

힙(Heap)은 원소를 정해진 규칙에 따라 배치한 완전 이진 트리로, 크게 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 구분할 수 있다. 최소 힙은 부모 노드의 값이 자식 노드의 값보다 작은 힙을 의미하며, 최대 힙은 그 반대이다. 형제 노드 간에는 대소 관계가 정해지지 않는다.

 

힙에 원소를 삽입하거나 힙에서 원소를 삭제할 경우 먼저 힙의 구조를 맞춘 다음 원소들의 교환을 통해서 대소 관계를 맞게 한다. 힙의 원소의 수가 $n$일 때 삽입/삭제 연산 한 번의 시간복잡도는 $\Theta(\text{lg }n)$이다.

 

이 힙을 이용해서 원소들을 정렬하는 것이 힙 정렬(Heap Sort)이다. 원소를 하나씩 힙에 삽입한 다음 힙의 루트에 있는 값을 빼는 과정을 반복하면 원소를 정렬할 수 있다. 정렬을 한 번 실행할 때 삽입 연산과 삭제 연산을 각각 $n$번 하게 되므로 전체 시간복잡도는 $\Theta(n\text{ lg }n)$이 된다.

 

다음은 힙 정렬을 시뮬레이션한 것이다.

힙 정렬은 최악의 경우에도 시간복잡도가 $\Theta(n\text{ lg }n)$이지만 메모리 접근의 측면에서 힙 정렬이 퀵 정렬보다 열세하고, 힙 정렬은 대체로 포인터를 많이 사용하다 보니 일반적인 경우 퀵 정렬이 힙 정렬보다 빠르게 동작한다.

 

→ solved.ac tag: sorting