ToB企服应用市场:ToB评测及商务社交产业平台

标题: 关于堆的一切 [打印本页]

作者: 石小疯 时间: 2024-5-11 22:51
标题: 关于堆的一切
前置知识

首先给出堆的定义：
堆是一颗树，满足堆的性质，即：
对于一个节点，它的权值大于（或小于）它的各个儿子的权值
有这个性质，显然
堆的根节点权值是整个堆中最大或最小的
由此可分为小根堆和大根堆
二叉堆

最常见的堆就是二叉堆
二叉堆是一颗满足堆的性质的完全二叉树
显然，二叉堆的子树也是二叉堆
接下来，我们以小根堆为例：
当一个节点权值小于其父亲时，我们尝试不断将这个节点与父亲交换，直到其满足堆的性质
这就是向上调整
同理，
当一个节点权值大于其父亲时，我们尝试不断将这个节点与其两个儿子中权值较小的一个交换，直到其满足堆的性质
这就是向下调整

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

由于堆的高度为 \(\log{n}\)
所以以上两个操作复杂度显然为 \(\mathcal {O}(\log{n})\)
那么有了这两个操作我们就可以完成：
插入（新建节点然后向上调整）
查询最大（最小）值（根节点权值）
删除最大（最小）值（与末尾节点交换，再向下调整）
删除任意节点（与末尾交换，再向上或向下调整，见代码）
修改任意节点权值（向上或向下调整）
Luogu （模板）堆
[code]#includeusing 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 > 1) { int fa = u >> 1; if (val[fa]

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)