Max Heap 자료구조를 이용하는 정렬로, 비어있는 Heap에 주어진 수열의 원소를 하나씩 삽입하면¹, 1차적으로 힙의 특성에 의한 정렬이 이뤄진다. 이를 우선순위 큐에서 꺼내듯이 큰 수부터 차례대로 pop하면, 정렬이 이뤄진다.

힙을 만드는데 드는 시간 과 pop에 필요한 시간 log을 합한 시간복잡도는 O() 이다.

Footnotes

1. 실제로는 하나씩 삽입하는 대신, 주어진 수열을 한 번에 힙으로 변환하는 in-place 알고리즘을 사용한다. ↩