Heap

Heap이란 입력으로 들어온 데이터를 2진 트리의 형태로 나타내어 순서대로 정렬? 해주는 것이라고 생각하면 쉬울 것이다.

자식 노드에 있는 값은 항상 부모노드의 값보다 작아야(혹은 정렬기준에 따라 커야) 함으로 입력과 동시에 정렬이 된다.

Heap을 사용하는 가장 대표적으로 사용하는 우선순위 queue, heap sort가 있다.

그 중에서도 heap sort를 구현해 보았으며, 정렬 기준을 함수로 선언하여 던져주는, 즉, algorithm 헤더에 있는 sort와 최대한 비슷하게 구현해보았다.

정의된 시간 복잡도는 heap sort는 O(nlogn)이다.

#include <iostream>
 
using namespace std;
 
int arr[10] = { 10, 49, 38, 17, 56, 92, 8, 1, 13, 55 };
 
void print(int *arr, const int *ed) {
    int size = ed - arr;
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    printf("\n");
}
 
bool com2(const int a, const int b) {
    return a > b;
}
 
bool com(const int a, const int b) {
    return a < b;
}
 
void h_sort(int *st, const int *ed, bool(*priorty)(const int, const int) = com) {
    const int size = ed - st;
    print(st, ed);
    for (int j = 0; j < size; j++) {
        for (int i = 0; i + j < size; i++) {
            int current = i;
            int prev = (current - 1) / 2;
            while (current > 0 && priorty(st[current + j], st[prev + j])) {
                int tmp = st[prev + j];
                st[prev + j] = st[current + j];
                st[current + j] = tmp;
                current = prev;
                prev = (current - 1) / 2;
            }
        }
    }
}
 
 
int main(void) {
 
    
    h_sort(arr, arr + 10, com2);
    print(arr, arr + 10);
 
    return 0;
}