[Computer Algorithms] Heap Sort (힙 정렬)

Heap

  힙의 대한 설명은 다음 글을 참고하자.

https://junstory314.tistory.com/entry/Data-Structures-Heap-%ED%9E%99

[Data Structures] Heap (힙)

 

Heap Sort

  힙 자료구조를 활용한 정렬이다.

1. 정렬하고자 하는 배열을 힙 구조로 변경한다. -> 시간 복잡도 : O(N)

2. 우선순위가 가장 높은 힙의 루트를 힙의 맨 끝으로 보내며, 이를 힙에서 제외한다. -> 시간 복잡도 : O(logN)

3. 2를 모든 노드가 힙에서 제외될 때 까지 반복한다. -> 시간 복잡도 : O(NlogN)

4. 완성된 배열은 정렬되어 있다. -> 최종 시간 복잡도는 O(NlogN)이며 Heap Sort는 in-place Sorting이다.

  HeapSort의 특성상 힙 구조를 만드는 과정과 힙에서 요소를 제거하는 과정에서 상대적인 순서가 고려되지 않기 때문에 Unstable하다.

 

 

Implementation

#include <iostream>
#include <vector>
#include "MaxHeap.cpp"
using namespace std;

int N;
Heap heap;

void input()
{
    cin >> N;
    heap = CreateHeap(N);
    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        Insert(heap, num);
    }
}

void heapSort()
{
    for (int i = 0; i < N; i++)
    {
        int maxVal = DeleteMax(heap);
        heap->elements[N - i] = maxVal;
    }
}

void output()
{
    for (int i = 1; i <= N; i++)
    {
        cout << heap->elements[i] << " ";
    }
    cout << endl;
}

int main(void)
{
    input();
    heapSort();
    output();
    return 0;
}

 

HeapSort는 최대 힙 또는 최소 힙의 루트값이 가장 크거나 가장 작은 값이기 때문에 이를 구할 때 유용하다.