[정렬] Heap Sort

힙 정렬은 주어진 데이터를 힙 형태로 만들어 최댓값/최솟값을 하나씩 꺼내서 정렬하는 알고리즘이다.

완전이진트리 형태로 최대 힙의 경우, 노드는 child 노드보다 항상 크거나 같은 값을 가지며, 최소 힙은 반대이다.

 

heapify 함수를 모든 노드에 대해 반복해 힙 구조로 만들어주는데,

최소 힙을 위한 heapify는 다음과 같은 로직으로 구현된다.

0번째 노드를 heapify 한다고 할 때,

0번째 노드의 child 노드 중 더 작은 값을 가진 노드(1번째로 가정)와 0번째 노드의 값을 비교해 0번째 노드의 값이 더 크면 교체한다.

이제 0번째 노드가 아니라 1번째 노드에 해당 숫자가 존재하므로, 1번째 수로 heapify를 계속 한다.

그럼 이 작업을 노드가 범위를 벗어나기 전까지, 또는 자식 노드가 없거나 자식 노드의 값이 이 노드보다 크거나 같을 동안 반복한다.

 

pop 연산도 마찬가지로 하향식 heapify를 거치게 되는데,

root 노드를 삭제하고 출력한 뒤,

그 자리에 마지막에 있던 노드를 올려 heapify를 0번 노드에 대해 진행한다.

---

#include <iostream>
#include <vector>

using namespace std;

int N;

// heapify => 자신의 자식 노드 중에서 더 큰 자식과 자신의 위치를 바꾸는 것.(최대 힙이 되도록 할 경우)
// 이 과정을 모든 원소를 기준으로 하면 heap이 완성됨.
// 여기선 최소 힙을 구성
// 자식노드 = 부모노드*2+1, 부모노드*2+2
void heapify(int arr[], int cur){
    // cur 노드를 하향식으로 heapify
    while(cur < N){
        int l_child = cur*2+1, r_child = cur*2+2;
        // left child, right child 모두 존재할 경우
        if(l_child < N && r_child < N){
            // 둘중 더 작은 값 가져오기
            int change = (arr[l_child] < arr[r_child]? l_child : r_child);
            // 더 작은 값이 cur의 값보다 작으면 교환.
            if(arr[change] < arr[cur]){
                int tmp = arr[cur];
                arr[cur] = arr[change];
                arr[change] = tmp;
                cur = change;
            }
            else{
                break;
            }
        }
        // left child만 존재하고 이 값이 cur의 값보다 작은 경우
        else if(l_child < N && arr[cur] > arr[l_child]){
            // cur과 교환
            int tmp = arr[cur];
            arr[cur] = arr[l_child];
            arr[l_child] = tmp;
            cur = l_child;
        }
        // right child만 존재하고 이 값이 cur의 값보다 작은 경우
        else if(r_child < N && arr[cur] > arr[r_child]){
            // cur과 교환
            int tmp = arr[cur];
            arr[cur] = arr[r_child];
            arr[r_child] = tmp;
            cur = r_child;
        }
        else{
            break;
        }
    }
}

int pop(int arr[]){
    // root 제거
    int ret = arr[0];
    N--;
    // root에 제일 마지막 값 올리기
    arr[0] = arr[N];
    // 하향식 heapify
    heapify(arr, 0);

    return ret;
}

int main(void){
    N = 10;
    int arr[10] = {2, 1, 9, 3, 4, 7, 2, 8, 10, 5};

    for(int i = 0; i < 10; i++)
        heapify(arr, i);

    for(int i = 0; i < 10; i++){
        cout << arr[i] << " ";
    }
    cout << endl;

    for(int i = 0; i < 10; i++){
        cout << pop(arr) << " ";
    }
    cout << "\n";

    return 0;
}