关于堆的一切-Toy模板网

这篇具有很好参考价值的文章主要介绍了关于堆的一切。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前置知识

首先给出堆的定义：
堆是一颗树，满足堆的性质，即：
对于一个节点，它的权值大于（或小于）它的各个儿子的权值

有这个性质，显然
堆的根节点权值是整个堆中最大或最小的
由此可分为小根堆和大根堆

二叉堆

最常见的堆就是二叉堆
二叉堆是一颗满足堆的性质的完全二叉树
显然，二叉堆的子树也是二叉堆

接下来，我们以小根堆为例：

当一个节点权值小于其父亲时，我们尝试不断将这个节点与父亲交换，直到其满足堆的性质
这就是向上调整

同理，
当一个节点权值大于其父亲时，我们尝试不断将这个节点与其两个儿子中权值较小的一个交换，直到其满足堆的性质
这就是向下调整

为什么这里要与权值较小的一个交换呢？
因为我们要使交换后满足堆的性质
所以新的父节点权值应小于它的两个儿子

由于堆的高度为 \(\log{n}\)
所以以上两个操作复杂度显然为 \(\mathcal {O}(\log{n})\)

那么有了这两个操作我们就可以完成：
插入（新建节点然后向上调整）
查询最大（最小）值（根节点权值）
删除最大（最小）值（与末尾节点交换，再向下调整）
删除任意节点（与末尾交换，再向上或向下调整，见代码）
修改任意节点权值（向上或向下调整）

Luogu （模板）堆

#include<bits/stdc++.h>

using namespace std;

static constexpr int AwA = 1e6 + 10;

inline static int Read() {
    int res = 0;
    bool flag = false;
    int c = getchar();
    while ((c < '0' || c > '9') && ~c) {
        flag |= c == '-';
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        res = (res << 1) + (res << 3) + (c ^ 48);
        c = getchar();
    }
    return flag ? -res : res;
}

//这里我们认为一个节点的父亲是u<<1，左儿子为u>>1，右儿子为u>>1|1
//根为1
//由堆为完全二叉树的性质可得只需开一倍数组
int val[AwA];
//储存总节点数
int len;

inline void MoveUp(int u) {
    while (u >> 1) {
        int fa = u >> 1;
        if (val[fa] <= val[u]) break;
        swap(val[fa], val[u]);
        u = fa;
    }
}

inline void MoveDown(int u) {
    while (u << 1 <= len) {
        int son = u << 1;
        if (son < len && val[son | 1] < val[son]) son |= 1;
        if (val[u] <= val[son]) break;
        swap(val[u], val[son]);
        u = son;
    }
}

inline int GetTop() { return val[1]; }

inline void Pop() {
    swap(val[1], val[len]);
    len--;
    MoveDown(1);
}

inline void Push(int _val) {
    val[++len] = _val;
    MoveUp(len);
}

//删除任意已知节点
inline void Delete(int u) {
    swap(val[u], val[len]);
    len--;
    if (val[u << 1] <= val[u]) MoveDown(u);
    else MoveUp(u);
}

//每次对于根进行向下调整，来合并左右儿子代表的两个堆
//OIwiki上有证明，这种建树是O(n)的
inline void Build(int _len, const int *a) {
    len = _len;
    memcpy(val + 1, a + 1, sizeof(int) * len);
    //叶子节点不调整，减小常数
    for (int i = (len >> 1) - 1; i; i--) MoveDown(i);
}

int main() {
    int n = Read();
    while (n--) {
        int op = Read();
        if (op == 1) Push(Read());
        else if (op == 2) printf("%d\n", GetTop());
        else Pop();
    }
    return 0;
}

此外，对于这段代码，我们来仔细讨论一下：

inline void Build(int _len, const int *a) {
    len = _len;
    memcpy(val + 1, a + 1, sizeof(int) * len);
    for (int i = (len >> 1) - 1; i; i--) MoveDown(i);
}

这段代码可以在 \(\mathcal {O}(n)\) 时间内建堆
我们按照节点bfs序倒序向下调整
每当调整到一个节点时
该节点的左右儿子所在子树已然是二叉堆
这时再把根节点向下调整满足堆的性质
可视为左右儿子代表的二叉堆的合并

证明：
待补充