堆,是优先队列最常用的一种实现方式。在优先队列中,每个元素都被赋予了一个优先级,而每次出队时都让优先级最高的元素出队。堆,则是一种存储优先队列的方法,特指以一棵树形式存储的优先队列。最常用的是二叉堆,但既然是专门介绍数据结构,就不妨说全一些,我们取4个典型的堆进行比较,见下表(此表及表下备注,来自于广东省中山市第一中学黄源河前辈的《左偏树的特点及其应用》,并做过言辞修改及内容补充):
项目 |
二叉堆 |
左偏树 |
二项堆 |
Fibonacci堆 |
构建 |
O(n) |
O(n) |
O(n) |
O(n) |
插入 |
O(logn) |
O(logn) |
O(logn) |
O(1) |
取最小点 |
O(1) |
O(1) |
O(logn) |
O(1) |
删除最小点 |
O(logn) |
O(logn) |
O(logn) |
O(logn) |
删除任意点 |
O(logn) |
O(logn) |
O(logn) |
O(logn) |
合并 |
O(n) |
O(logn) |
O(logn) |
O(1) |
空间需求 |
最小 |
较小 |
一般 |
较大 |
编程复杂度 |
最低 |
较低 |
较高 |
很高 |
在此说明几点:
0、二项堆又称Bernoulli堆,左偏树又称左堆;斜堆并未在表中列出,是由于其复杂度与左偏树相同,没必要单独列出。其代码更简单,但常数较大,且在特殊数据下可能退化成O(n)。它与左偏树的关系,就像Splay与AVL的关系,并无优劣之分,前者更简洁灵活而后者更快。另外,我并未谈及D堆,那是因为这类仅在接触外存才值得应用的堆,我并不想提及。大家在考试用不上,平时也用不上,故而在我看来暂时了解、理解就好,之后真正用到了再去深究不迟。
1、二项堆,其“取最小点”的复杂度是O(log n),可以改进为O(1)。方法是,随时记录最小节点,并只在插入、删除以及合并等操作进行的时候更新该记录。
2、二项堆,其“插入”操作的平均时间复杂度为O(1),表中给出的是最坏时间复杂度。
3、Fibonacci堆,其“删除最小点”和“删除任意点”两个操作的时间复杂度均为平摊时间复杂度。
可能大家并未了解全,那就请自行搜索吧,我在此仅仅给出实现代码。由于种类过多,我仅仅对每种堆给出一种最常见的实现方式(例如二叉堆仅仅给出数组实现法),大家视题目需要而融会贯通即可。另外,由于代码较长,为了方便大家比较,我仅仅给出类版,实际实现时,不写成类有时反而方便许多。
还有,我依旧假设每个元素的信息仅有一个int权值,这样可以让大家更关注代码的框架结构,而不至于在繁琐的代码中看得迷迷糊糊。真正使用时,如果元素信息增多,视情况修改即可。
未经允许不得转载!《数据结构》C++代码 堆(优先队列)