[자료구조]minHeap, 최소힙구현

최소 힙을 구현해보았다. 

최소 힙은 완전이진트리를 구조를 기본으로 한다.

최소 힙은 아래 속성을 만족하면 된다.

- 부모노드가 자식노드보다 키값이 더 작아야 한다.

#include<iostream>
const int ROOT = 1;
const int MAX = 1 << 15;
struct minheap {
    int data[MAX];
    int element;
    int capacity;
    minheap() {
        element = 0;
        capacity = MAX;
    }
    bool empty() {
        return element == 0;
    }
    bool full() {
        return element == MAX;
    }
    void push(int input) {
        if (full()) return;
        data[++element] = input;
        int child = element;
        bool is_ok = true;
        while ((child / 2) > 0 && is_ok) {
            if (data[child] < data[child / 2]) {
                swap(child, child / 2);
                child = child / 2;
            } // 부모노드와 비교
            else {
                is_ok = false;
            }
        }
    }
    void pop() {
        if (empty()) return;
        data[ROOT] = data[element];
        element--;
        int parent = ROOT;
        int is_ok = true;
        while (2 * parent <= element && is_ok) {
            if (data[2 * parent] <= data[2 * parent + 1] && data[2 * parent] < data[parent]) {
                swap(parent, 2 * parent);
                parent = 2 * parent;
            } // 좌측자식노드와 비교 
            else if (data[2 * parent + 1] < data[2 * parent] && data[2 * parent + 1] < data[parent]) {
                swap(parent, 2 * parent + 1);
                parent = 2 * parent + 1;
            } // 우측자식노드와 비교
            else {
                is_ok = false;
            } // 아닌 경우 
        }
    }
    int top() {
        if (empty()) return -1;
        return data[ROOT];
    }
private:
    void swap(int a, int b) {
        int temp = data[a];
        data[a] = data[b];
        data[b] = temp;
    }
};
 
int main() {
    minheap H;
    for (int i = 21; i > 0; i /= 2) {
        H.push(i);
        printf("%d\n", H.top());
    }
    puts("pop");
    for (int i = 0; i < 10; i++) {
        printf("%d\n", H.top());
        H.pop();
    }
    return 0;
}

struct minheap {
    int d[1 << 18];
    int e;
    minheap() { e = 0; }
    bool empty() { return e == 0; }
    bool full() { return (e + 1) == (1 << 18); }
    void push(int i) {
        if (full()) return;
        d[++e] = i;
        int cur = e;
        while (cur / 2 > 0) {
            if (d[cur] < d[cur / 2]) swap(d[cur], d[cur / 2]);
            else break;
            cur = cur / 2;
        }
    }
    void pop() {
        if (empty()) return;
        d[1] = d[e];
        e--;
        int cur = 1;
        while (2 * cur <= e) {
            int child;
            if (2 * cur + 1 > e) {
                child = 2 * cur;
            }
            else {
                child = (d[2 * cur] < d[2 * cur + 1]) ? 2 * cur : 2 * cur + 1;
            }
 
            if (d[cur] < d[child]) break;
            swap(d[cur], d[child]);
            cur = child;
        }
    }
    int top() {
        if (empty()) return -1;
        return d[1];
    }
    void swap(int& a, int& b) {
        int t = a;
        a = b;
        b = t;
    }
    void clear() { e = 0; }
};