水资源论证网站建设,莱芜论坛二手车,宝山专业网站建设,深圳网站seo公司数据结构——堆 堆堆简介堆的分类 二叉堆过程插入操作 删除操作向下调整#xff1a; 增加某个点的权值实现参考代码#xff1a;建堆方法一#xff1a;使用 decreasekey#xff08;即#xff0c;向上调整#xff09;方法二#xff1a;使用向下调整 应用对顶堆 其他#… 数据结构——堆 堆堆简介堆的分类 二叉堆过程插入操作 删除操作向下调整 增加某个点的权值实现参考代码建堆方法一使用 decreasekey即向上调整方法二使用向下调整 应用对顶堆 其他配对堆:左偏树: 堆
堆简介
堆是一棵树其每个节点都有一个键值且每个节点的键值都大于等于/小于等于其父亲的键值。
每个节点的键值都大于等于其父亲键值的堆叫做小根堆否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。
小根堆主要支持的操作有插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。
一些功能强大的堆可并堆还能高效地支持 merge 等操作。
一些功能更强大的堆还支持可持久化也就是对任意历史版本进行查询或者操作产生新的版本。
堆的分类 习惯上不加限定提到「堆」时往往都指二叉堆。
二叉堆
结构 从二叉堆的结构说起它是一棵二叉树并且是完全二叉树每个结点中存有一个元素或者说有个权值。
堆性质父亲的权值不小于儿子的权值大根堆。同样的我们可以定义小根堆。本文以大根堆为例。
由堆性质树根存的是最大值getmax 操作就解决了。
过程
插入操作
插入操作是指向二叉堆中插入一个元素要保证插入后也是一棵完全二叉树。
最简单的方法就是最下一层最右边的叶子之后插入。
如果最下一层已满就新增一层。
插入之后可能会不满足堆性质
向上调整如果这个结点的权值大于它父亲的权值就交换重复此过程直到不满足或者到根。
可以证明插入之后向上调整后没有其他结点会不满足堆性质。
向上调整的时间复杂度是 O ( l o g n ) O(log n) O(logn)的。
删除操作
删除操作指删除堆中最大的元素即删除根结点。
但是如果直接删除则变成了两个堆难以处理。
所以不妨考虑插入操作的逆过程设法将根结点移到最后一个结点然后直接删掉。
然而实际上不好做我们通常采用的方法是把根结点和最后一个结点直接交换。
于是直接删掉在最后一个结点处的根结点但是新的根结点可能不满足堆性质……
向下调整
在该结点的儿子中找一个最大的与该结点交换重复此过程直到底层。
可以证明删除并向下调整后没有其他结点不满足堆性质。
时间复杂度 O ( l o g n ) O(log n) O(logn)。
增加某个点的权值
很显然直接修改后向上调整一次即可时间复杂度为 O ( l o g n ) O(log n) O(logn)。
实现
我们发现上面介绍的几种操作主要依赖于两个核心向上调整和向下调整。
考虑使用一个序列 h h h 来表示堆。 h i h_i hi 的两个儿子分别是 h 2 h_2 h2 i _i i 和 h 2 h_2 h2 i _i i _ 1 _1 1 1 1 1 是根结点 参考代码
void up(int x) {while (x 1 h[x] h[x / 2]) {swap(h[x], h[x / 2]);x / 2;}
}void down(int x) {while (x * 2 n) {t x * 2;if (t 1 n h[t 1] h[t]) t;if (h[t] h[x]) break;std::swap(h[x], h[t]);x t;}
}建堆
考虑这么一个问题从一个空的堆开始插入 n 个元素不在乎顺序。
直接一个一个插入需要 O ( n l o g n ) O(n log n) O(nlogn) 的时间有没有更好的方法
方法一使用 decreasekey即向上调整
从根开始按 BFS 序进行。
void build_heap_1() {for (i 1; i n; i) up(i);
}为啥这么做对于第 k 层的结点向上调整的复杂度为 O ( k ) O(k) O(k) 而不是 O ( l o g n ) O(log n) O(logn)。
总复杂度 l o g 1 log 1 log1 l o g 2 log 2 log2 … l o g n log n logn O ( n l o g n ) O(n log n) O(nlogn)。
在「基于比较的排序」中证明过
方法二使用向下调整
这时换一种思路从叶子开始逐个向下调整
void build_heap_2() {for (i n; i 1; i--) down(i);
}换一种理解方法每次「合并」两个已经调整好的堆这说明了正确性。
注意到向下调整的复杂度为 O ( l o g n − k ) O(log n - k) O(logn−k)另外注意到叶节点无需调整因此可从序列约 n/2 的位置开始调整可减少部分常数但不影响复杂度。
之所以能 O ( n ) O(n) O(n) 建堆是因为堆性质很弱二叉堆并不是唯一的。 要是像排序那样的强条件就难说了。
应用
对顶堆
这个问题可以被进一步抽象成动态维护一个序列上第 k k k 大的数 k k k 值可能会发生变化。
对于此类问题我们可以使用对顶堆这一技巧予以解决可以避免写权值线段树或 B S T BST BST带来的繁琐。
对顶堆由一个大根堆与一个小根堆组成小根堆维护大值即前 k k k 大的值包含第 k k k 个大根堆维护小值即比第 k k k 大数小的其他数。
这两个堆构成的数据结构支持以下操作
1.维护当小根堆的大小小于 k k k 时不断将大根堆堆顶元素取出并插入小根堆直到小根堆的大小等于 k k k当小根堆的大小大于 k k k 时不断将小根堆堆顶元素取出并插入大根堆直到小根堆的大小等于 k k k
2.插入元素若插入的元素大于等于小根堆堆顶元素则将其插入小根堆否则将其插入大根堆然后维护对顶堆
3.查询第 k 大元素小根堆堆顶元素即为所求
4.删除第 k 大元素删除小根堆堆顶元素然后维护对顶堆
显然查询第 k k k 大元素的时间复杂度是 O ( 1 ) O(1) O(1) 的。由于插入、删除或调整 k k k 值后小根堆的大小与期望的 k k k 值最多相差 1 1 1故每次维护最多只需对大根堆与小根堆中的元素进行一次调整因此这些操作的时间复杂度都是 O ( l o g n ) O(log n) O(logn) 的。
其他
配对堆:
详见链接: 数据结构——配对堆
左偏树:
详见后文。
