힙 정렬

힙 자료구조를 이용하는 정렬.

O(nlogn)의 시간복잡도를 가진다.

 

맨 마지막 인덱스부터 정렬한다.

void HeapSort(vector<int>& v)
{
    priority_queue<int, vector<int>, greater<int>> pq;

    // O(NlogN)
    // pq 에 데이터를 push 할 때는 시간 복잡도 logN이다.
    // 그러나 여기서는 v의 모든 요소 N 개를 집어넣으니 NlogN이다.
    for (int num : v)
        pq.push(num);

    v.clear();

    // O(NlogN)
    // 위와 같음
    while (!pq.empty())
    {
        v.push_back(pq.top());
        pq.pop();
    }
}