手写堆

原理

见《进阶指南》第80页。

代码

const int N = 100010;
struct priority_queue { // 大顶堆
    int n, heap[N];
    int top() { return heap[1]; }
    bool empty() { return n == 0; }
    void up (int ptr) {
        while (ptr > 1) {
            if (heap[ptr] > heap[ptr / 2]) {
                swap(heap[ptr], heap[ptr / 2]);
                ptr /= 2;
            } else {
                break;
            }
        }
    }
    void down (int ptr) {
        int k = ptr * 2;
        while (k <= n) {
            if (k < n && heap[k] < heap[k + 1]) ++ k;
            if (heap[k] > heap[ptr]) {
                swap(heap[k], heap[ptr]);
                ptr = k;
                k = ptr * 2;
            } else {
                break;
            }
        }
    }
    void push (int val) {
        heap[++ n] = val;
        up(n);
    }
    void pop () {
        heap[1] = heap[n --];
        down(1);
    }
    void modify (int idx, int val) {
        heap[idx] = val;
        up(idx);
        down(idx);
    }
    void remove (int idx) {
        heap[idx] = heap[n --];
        up(idx);
        down(idx);
    }
};
priority_queue pq;