[Algorithm] Sort #5 - 힙 정렬 Heap Sort

힙 정렬이란?

 힙 자료구조의 루트를 뽑아 정렬하는 알고리즘

 

시간 복잡도

최상 : $O(n\log n)$

최악 : $O(n\log n)$

 

관련 글

[Algorithm] Sort #1 - 버블 정렬 Bubble Sort

[Algorithm] Sort #2 - 선택 정렬 Selection Sort

[Algorithm] Sort #3 - 삽입 정렬 Insertion Sort

[Algorithm] Sort #4 - 병합 정렬 Merge Sort

[Algorithm] Sort #6 - 퀵 정렬 Quick Sort

 

---

 

 병합 정렬에 이어서 평균 시간 복잡도가 $O(n^2)$인 정렬 알고리즘 중 두번째는 힙 정렬입니다. 자료구조 중에서 힙(heap)의 특성을 이용해 정렬을 구현한 알고리즘입니다. 선택 정렬과 같이 원소 중에서 최솟 값을 찾아 순차적으로 정렬 시키지만 최솟 값을 찾기 위해 힙을 사용한다는 점이 차이점입니다.

 

힙(heap)  완전 이진트리의 자료구조로 최소 힙, 최대 힙이 있다. 최소, 최대 힙에 따라 부모 노드는 자식 노드보다 항상 작은 값이나 큰 값을 가진다. 삽입, 삭제의 경우 $O(\log n)$의 시간이 걸린다.

 

알고리즘

 힙 정렬의 알고리즘은 다음과 같습니다.

1. 리스트의 원소들을 모두 힙에 넣는다.
2. 힙의 루트 원소를 뽑아 정렬 시킬 배열에 넣고 힙에서는 제거한다.
3. 2의 과정을 n번 진행한다.

 

힙 정렬 예시

 { 9, 1, 7, 5, 2} 순서대로 원소가 존재한다고 가정했을 때 힙 정렬의 예시는 다음과 같습니다. {9, 1, 7, 5, 2}의 원소들을 순서대로 힙에 삽입하는 작업을 진행하고 삽입 결과 힙의 구조는 아래와 같습니다. 힙이 만들어졌다면 루트의 값을 배열에 순차적으로 넣는 작업을 n번 진행합니다.

 

 

 

시간 복잡도 계산

 힙 정렬의 시간복잡도는 최악, 최상의 경우가 같습니다.

 

힙 구성

 먼저 리스트의 원소들을 가지고 힙을 만들어주는 작업이 필요합니다. 힙의 삽입에 걸리는 시간은 $O(\log n)$이므로 총 $O(n\log n)$의 시간이 걸립니다.

 

리스트 정렬

 힙의 구성이 완료되었다면, 루트의 값을 저장 후 삭제하는 작업이 필요합니다. 힙의 삭제에 걸리는 시간 또한 $O(\log n)$이고 이 과정을 총 n번 하기 때문에 $O(n\log n)$의 시간이 걸립니다.

 

 이전 글에서 병합 정렬은 리스트의 상태에 관계 없이 $O(n\log n)$의 시간 복잡도를 가진다고 설명했습니다. 이와 마찬가지로 힙 정렬도 리스트의 상태에 관계 없이 일정하게 $O(n\log n)$의 시간 복잡도를 가집니다.

 

C++ Code

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int main()
{
    vector<int> arr = {9,1,7,5,2};
    
    priority_queue<int, vector<int>, greater<int>> heap;
    
    for(int i=0; i<arr.size(); i++)
        heap.push(arr[i]);
        
    for(int i=0; i<arr.size(); i++){
        arr[i] = heap.top();
        heap.pop();
    }
    
    for(int i=0; i<arr.size(); i++)
        cout << arr[i];
}