二叉堆 | Yuhang's Blog

C++中可以使用priority_queue的二叉堆。

定义和引理

二叉堆是满足如下性质的完全二叉树：

任意父亲大于等于（或小于等于）其儿子。（性质1）

我们这里以大根堆为例。不难由性质1推得，并在它的命名中得到确认：在大根堆之中，根是整棵树中最大的元素。大根堆的用处：插入一个数；查询或删除最大数。完全二叉树样例如果将完全二叉树的所有节点从上到下、从左到右由1到$n$进行编号，那么：

若$u>1$，则$\lfloor u/2 \rfloor$是$u$的父亲。
$2u$和$2u+1$分别是$u$的左右儿子，前提是它们各自不超过$n$。

将它们按照编号存放在一个数组中是常见的实现方式。

插入和查询

定义percolateUp和percolateDown两个操作如下。

percolateUp：当整棵树——除了一个叶子节点——均满足性质1时，不断尝试将这个节点与它的父亲互换，直到它成为根或性质1得到满足；
percolateDown：当整棵树——除了根节点——均满足性质1时，不断尝试将这个节点与它的较大的儿子进行互换，直到它成为叶子节点或性质1得到满足。注意，由于每次均和较大的儿子进行互换，所以这个儿子可以成为另一个（较小的）儿子的父亲；此时问题被化归为原先的较大的儿子的子树的问题。

这两个操作的时间复杂度都是$O(\log(n))$的。那么：

查询最大元素，即为根；
要插入一个元素的时候，将新来的元素放在一个新的叶子上，然后执行percolateUp操作；
要删除根的时候，将编号最大的叶子覆盖在根上、并删除这个叶子，然后执行percolateDown操作。

建堆

建堆就是插入$n$个数，过程中不会涉及查询和删除。显然可以通过进行$n$次插入操作来完成建堆，时间复杂度是$O(n \log (n))$. 可以进行优化。首先将$n$个数随意填入完全二叉树中。注意到此时对于所有以叶子为根的子树，均满足性质1（当然了，那是因为在这种子树内并不存在父子关系）；接下来考虑所有以某个叶子的父亲为根的子树，这些子树均满足percolateDown的执行前提，因此可以对它们进行一次percolateDown操作，从而使这些子树分别满足性质1；这时所有以从下向上数第三层的节点为根的子树又都可以进行percolateDown操作……以此类推，直到整棵树均满足性质1. 可以证明该算法复杂度是$O(n)$的。

实现

const int N = 150100;
bool my_greater(int x, int y) { return x > y; }
bool my_less(int x, int y) { return x < y; }
struct Heap {
    int n; int a[N];
    bool (*cmp)(int, int);
    Heap(bool (*_cmp)(int, int)) : cmp(_cmp) {} ;

    void percolateUp(int u) {
        while (u > 1 && cmp(a[u], a[u >> 1])) swap(a[u], a[u >> 1]), u >>= 1;
    }

    void percolateDown(int u) {
        for (int v = u << 1; v <= n; u = v, v = u << 1) {
            if (v + 1 <= n && cmp(a[v + 1], a[v])) v++;
            if (!cmp(a[v], a[u])) break;
            swap(a[v], a[u]);
        }
    }

    void insert(int x) {
        a[++n] = x;
        percolateUp(n);
    }

    void pop() {
        a[1] = a[n--];
        percolateDown(1);
    }

    void add(int x) { a[++n] = x; }
    void build() { 
        for (int i = n >> 1; i >= 1; i--) percolateDown(i); 
    }

    int top() { return a[1]; }
    int size() { return n; }
    void clear() { n = 0; }
};

应用：对顶堆

支持插入；支持查询、删除第$k$大的数；$k$可以发生变化。从而可以应用到求中位数。用维护一个大根堆和一个小根堆来实现。解释请参考二叉堆 - OI Wiki，就不复制了。这里给出一个维护中位数的实现，原题SP16254 RMID2 - Running Median Again - 洛谷：

struct KHeap {
    Heap h1 = Heap(my_greater);
    Heap h2 = Heap(my_less);

    void maintain() {
        int n = h1.size() + h2.size();
        int k = (n + 1) / 2;
        while (h1.size() < k) {
            h1.insert(h2.top()); h2.pop();
        }

        while (h1.size() > k) {
            h2.insert(h1.top()); h1.pop();
        }
    }

    void insert(int x) {
        if (h1.size() == 0  x <= h1.top()) {
            h1.insert(x);
        } else {
            h2.insert(x);
        }

        maintain();
    }

    int query() {
        return h1.top();
    }

    void remove() {
        h1.pop();
        maintain();
    }

    void clear() {
        h1.clear(); h2.clear();
    }
};