최소힙(Min Heap) 구현

Joonas' Note

최소힙(Min Heap) 구현 본문

알고리즘/자료구조

최소힙(Min Heap) 구현

2020. 2. 22. 00:02 joonas 읽는데 1분

    이진 트리 중에서도 힙.

    힙 중에서도 최소힙을 구현한 코드

    ////////////////////////////////////////////
    // @title Implement of Min-Heap
    // @author Joonas <joonas.yoon@gmail.com>
    // @blog https://joonas.tistory.com
    ////////////////////////////////////////////
    #define MAX_SIZE 100001
    template <typename T>
    class MinHeap {
    private:
    int sz;
    T a[MAX_SIZE];
    public:
    MinHeap() {
    sz = 0;
    }
    bool empty() {
    return sz == 0;
    }
    void clear() {
    sz = 0;
    }
    T top() { // or peek()
    return a[0];
    }
    void pop() {
    a[0] = a[--sz];
    heapify(0);
    }
    void push(T data) {
    a[sz] = data;
    for (int i = sz++; i;) {
    int p = (i - 1) >> 1;
    if (a[p] < a[i]) break;
    swap(a[p], a[i]);
    i = p;
    }
    }
    private:
    void heapify(int p) {
    int l = 2 * p + 1;
    int r = l + 1;
    int k = p;
    if (l < sz && a[l] < a[k]) k = l;
    if (r < sz && a[r] < a[k]) k = r;
    if (k != p) {
    swap(a[k], a[p]);
    heapify(k);
    }
    }
    };
    view raw heap.cpp hosted with ❤ by GitHub

    C++에서 대소비교에 기본값인 less than(<) 연산만 사용하여 구현했기 때문에, < 연산자만 오버로딩한다면, 다른 구조체/클래스도 무난하게 동작한다.