binary heap

max heap

#include <bits/stdc++.h>
using namespace std;

template<typename T>
class MaxPQ {
public:
    MaxPQ(int cap) {
        pq = new T[cap+1];
    }

    T max() {
        return pq[1];
    }

    void swim(int i) {
        while (i > 1 && less(parent(i), i)) {
            exchange(parent(i), i);
            i = parent(i);
        }
    }

    void sink(int i) {
        while (left(i) <= N) {
            int older = left(i);
            if (right(i) <= N && less(older, right(i))) {
                older = right(i);
            }
            if (less(older, i)) {
                break;
            }
            exchange(i, older);
            i = older;
        }
    }

    void insert(T e) {
        N++;
        pq[N] = e;
        swim(N);
    }

    T delMax() {
        T max = pq[1];
        exchange(1, N);
        pq[N] = (T)nullptr;
        N--;
        sink(1);
        return max;
    }

private:
    T* pq = nullptr;
    int N = 0;          // N is current size not capability

    bool less(int i, int j) {
        return pq[i] < pq[j];
    }

    void exchange(int i, int j) {
        T tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;
    }

    int parent(int root) {
        return root / 2;
    }

    int left(int root) {
        return root * 2;
    }

    int right(int root) {
        return root * 2 + 1;
    }
};

int main(void) {
    MaxPQ<int> pq(10);
    pq.insert(3);
    cout << pq.max() << endl;
    pq.insert(5);
    cout << pq.max() << endl;
    pq.insert(1);
    cout << pq.max() << endl;
    pq.delMax();
    cout << pq.max() << endl;
    pq.delMax();
    cout << pq.max() << endl;

    cout << endl;
}

3
5
5
3
1

感谢大二数据结构课偷偷瞄了几眼严奶奶的书。
通过上浮和下沉操作维护二叉堆性质，至于为啥分上浮和下沉，我觉得可能是出于方便insert和delete的考虑，insert插到堆底一直上浮就行，delete呢，算法设计得很妙，堆顶下沉方便，堆底上浮方便，删堆顶只要交换堆顶堆底并下沉当前堆顶即可维护二叉堆性质。