[C++] Heap 자료구조

최대값 혹은 최솟값을 빨리 뽑아내고 싶으면 사용하는 자료구조이다. 최대값을 빨리 뽑도록 자료를 저장해 Max Heap이라고 불리고 최솟값을 빨리 뽑도록 자료를 저장한 것은 Min Heap이라고 한다.

Heap를 이용해 min 값을 뽑으면 O(log n)이 걸린다.

 

특징

1. 이진트리 형태로 값을 저장한다

2. root에는 항상 Min 값이 있어야 한다. Push와 pop를 할때도 Min값은 항상 유지된다.

 

#include <iostream>
#include <unordered_map>
using namespace std;

int heap[100];
int hn;

void push(int value) {
    //트리의 맨 뒤에 value 값을 넣는다.
    heap[++hn] = value;
    int now = hn;
    int parent;
    while (1) {
        // 부모의 index= 자신의 index / 2
        parent = now / 2;

        // now가 root이면 부모가 없기에 swap하지 않는다.
        if (now == 1)break;

        // now가 부모보다 같거나 클 경우 swap하지 않는다.
        if (heap[parent] <= heap[now])break;

        swap(heap[parent], heap[now]);
        now = parent;
    }
}

int pop() {
    int backup = heap[1];
    heap[1] = heap[hn];
    heap[hn--] = 0;

    int now = 1;
    int son;

    while (1) {
    
        // 첫째 자식 선택
        son = now * 2;

        // 첫째랑 둘째중 작은 값을 선택
        if (son + 1 <= hn && heap[son] > heap[son + 1])son++;

        // 자식이 없거나, 자식이 부모보다 크거나 값은 값을 갖고있으면 swap하지 않는다.
        if (son > hn || heap[son] >= heap[now])break;

        swap(heap[now], heap[son]);
        now = son;
    }
    return backup;
}

int main() {

    push(3);
    push(5);
    push(2);
    push(4);
    push(1);
    push(6);

    cout << pop();
    cout << pop();
    cout << pop();
    cout << pop();
    cout << pop();
    cout << pop();

    return 0;
}