정렬 (sort) : 힙 정렬 (Heap sort)

원리

---

힙(heap)의 특징인 루트 노드가 가장 크다는 특징을 이용한 정렬입니다.
algorithm헤더에 있는 push_heap연산과 pop_heap연산을 이용하여 구현하였습니다. push_heap은 [frist, last) 범위에 데이터를 저장하고, pop_hepa은 first 인덱스와 last - 1인덱스의 값을 교환하여 힙을 구성합니다.

소스 코드 (구현)

---

#include <iostream>
#include <algorithm>

using namespace std;

template <typename T>
void heap_sort(T *start, T *end)
{
    for (T *pos = start + 2; pos < end; pos++)
        push_heap(start, pos);

    for (T *pos = end; pos >= start + 2; pos--)
        pop_heap(start, pos);
}

int main()
{
    int arr[5] = {13, 11, 51, 2, 7};

    heap_sort(arr, arr + 5);

    for (const auto r : arr)
    {
        cout << r << ' ';
    }

    return 0;
}

성능

---

• push할 때의 시간 복잡도는 \(O(nlog_2 n)\)이고, pop을 할 때의 시간 복잡도도 \(O(nlog_2 n)\)이므로 힙 정렬의 시간 복잡도는 \(O(nlog_2 n)\)입니다.
• unstable sort입니다.