힙 정렬

 

개념

힙 정렬은 힙을 통해 구현하는 정렬 알고리즘입니다. 힙이란 간단하게 말하자면 최댓값, 최솟값을 쉽게 추출해낼수 있는 자료구조입니다. 

이러한 힙트리를 구성해서 정렬을 하게 되는데, 오름차순 정렬을 위해서는 최소힙을 사용하고, 내림차순 정렬을 위해서는 최대힙을 사용합니다.

전체적인 과정은 다음과 같습니다.

1. 정렬해야할 다음 n개의 요소들로 최소 힙(완전 이진트리)을 만듭니다.
2. 그 다음으로 한번에 하나씩 요소를 힙에서 꺼내어 배열의 뒤에서부터 저장하면 됩니다. 
3. 삭제되는 요소들은 값이 증가하는 오름차순 형태로 정렬되게 됩니다.

다음은 내림차순 정렬을 위한 최대힙의 구조입니다.

 

 

코드

힙은 C++에서 priority_queue라는 우선순위 큐를 통해 이미 구현되어 있습니다. 

따라서 우선순위 큐를 사용하여 구현해 보겠습니다.

void heap_sort(vector<int>& arr){

    priority_queue<int,vector<int>,greater<>> pq;

    for(int i : arr){
        pq.push(i);
    }
    
    int i = 0;
   while(!pq.empty()){
       int x = pq.top();
       arr[i++] = x;
       pq.pop();
   }
}

 

힙정렬의 장점

- 시간복잡도가 좋은 편입니다.

- 힙 정렬이 가장 유용한 경우는 모든 요소들을 정렬시키는 것이 아닌 가장 큰 값 몇개만 필요할 때입니다. 

 

힙정렬의 시간복잡도

시간복잡도를 계산하기 위해서는 먼저 힙의 Insert와 Delete시에 드는 시간복잡도를 알아야 합니다. 

코드를 보면 알겠지만 정렬시에 Insert와 Delete는 각각 n번의 수행이 일어납니다. 

 

최대힙을 예시로 설명하겠습니다.

Insert: 삽입의 경우, 완전이진트리의 인덱스 순으로 가장 마지막 위치에 삽입을 합니다. 그 후 자신의 부모노드와 비교하면서 SWAP을 하며 자신의 위치를 찾아갑니다. 완전이진트리의 높이의 경우 자신의 요소들의 log2n을 유지하므로 적어도 log2n만큼의 비교가 일어난다고 볼수 있습니다.

 

Delete: 삭제의 경우, 루트노드를 삭제합니다. 이후 마지막 인덱스 값을 루트노드의 위치로 옮긴후, 자식노드들과 비교를 하면서 Swap을 합니다. 이때 자식노드들중 더 큰값과 Swap합니다. 제자리를 찾아갈때까지 자식노드들과 비교합니다. 이 또한 완전이진트리의 높이가 log2n이므로 적어도 log2n만큼만의 비교가 일어납니다. 

 

따라서 시간복잡도는 2 * N * log2N입니다. O(N*log2N)