[알고리즘] 힙 정렬(Heap Sort)

힙을 이용하여 힙 정렬을 할 경우 정렬 시간이 $n\log{n}$으로 크게 감소한다.

C++ 구현

#include <algorithm>
using namespace std;

template <class RandomIt>
void heap_sort(RandomIt first, RandomIt last)
{
    make_heap(first, last);
    for (RandomIt it = last; it != first; --it)
        pop_heap(first, it);
}

algorithm 헤더 파일의 heap과 관련된 함수를 이용하였다. [first, last) 범위의 원소를 오름차순으로 힙 정렬하는 코드이다.