在计算机科学中,堆是一种特殊的基于树的数据结构,本质上是一棵几乎完全的[1]树, 它满足堆属性:在最大堆中,对于任意给定的节点C,如果P是C的父节点,那么P的键(值)大于或等于C的键。在最小堆中,P的键小于或等于C的键。堆“顶部”的节点(没有父节点)称为根节点。
堆是称为优先队列的抽象数据类型的最有效实现,事实上优先队列通常被称为“堆”,不管它们是如何实现的。在堆中,最高(或最低)优先级的元素总是存储在根节点。然而,堆不是排序结构,它可以被认为是部分有序的。当需要重复移除优先级最高(或最低)的对象时,堆是一种有用的数据结构。
堆的一个常见实现是二叉堆,其中树是二叉树(见图)。堆数据结构,特别是二叉堆,是由J. W. J. Williams在1964年引入的,作为堆排序算法的数据结构。[2] 堆在一些高效的图算法中也很重要,比如Dijkstra算法。当堆是一棵完全二叉树时,它有一个最小的可能高度——一个有N个节点的堆,对于每个节点,一个分支总是有loga N 的高度。
注意,如图所示,兄弟和堂兄弟之间没有隐含的排序,也没有有序遍历的隐含序列(例如,在二叉搜索树中)。上面提到的堆关系仅适用于节点和它们的父亲、祖父等之间。每个节点可以拥有的最大子节点数取决于堆的类型。
涉及堆的常见操作有:
堆通常在数组(固定大小或动态数组)中实现,并且不需要元素之间的指针。元素插入堆或从堆中删除后,可能会违反堆性质,必须通过内部操作来平衡堆。
二叉堆可以用单独使用数组的非常节省空间的方式来表示。第一个(或最后一个)元素将包含根元素。数组接下来两个元素包含根元素的孩子。接下来的四个包含两个子节点的四个子节点,等等。因此,在位置n的节点的子节点将在以1为起点编号数组的2n和2n+1位置,或者“以0为起点编号数组的2n+1和2n+2位置。这允许通过简单的索引计算来向上或向下移动树。允许通过向上筛选或向下筛选操作(交换无序元素)来完成平衡堆。因为我们可以从一个数组构建一个堆,而不需要额外的内存(例如,对于节点),所以heapsort可以用来就地排序一个数组。
不同类型的堆以不同的方式实现操作,但值得注意的是,插入通常是通过在堆的末尾第一个可用空间中添加新元素来完成的。这通常会违反堆性质,因此元素会被向上筛选,直到堆性质被重新建立。类似地,删除根元素是通过移动根元素,然后将最后一个元素放入根并向下筛选以重新平衡。因此,替换是通过删除根并将新元素放入根并向下筛选来完成的,和先pop(向下筛选最后一个元素),再push(向上筛选新元素)后相比,避免了向上筛选步骤。
从给定的元素数组中构造二叉(或d叉)堆可以使用经典弗洛伊德算法在线性时间内执行,最差情况下的比较次数等于2N − 2s2(N) − e2(N) (对于二叉堆),其中 s2(N)是N的二进制表示的所有数字的总和,e2(N)是N的素数因子分解中的2的指数,[6] 这比连续插入原始空堆的序列更快,该操作是对数线性的。
以下是各种堆数据结构的时间复杂度。 函数名假设一个最小堆。
In the following time complexities[7] O(f) is an asymptotic upper bound and Θ(f) is an asymptotically tight bound (see Big O notation). Function names assume a min-heap.
Operation | Binary[7] | Leftist | Binomial[7] | Fibonacci[7][8] | Pairing[9] | Brodal[10] | Rank-pairing[11] | Strict Fibonacci[12] | 2-3 heap |
---|---|---|---|---|---|---|---|---|---|
find-min | Θ(1) | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | ? |
delete-min | Θ(log n) | Θ(log n) | Θ(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
insert | O(log n) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | O(log n) |
decrease-key | O(log n) | Θ(n) | Θ(log n) | Θ(1) | o(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
merge | Θ(n) | Θ(log n) | O(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | ? |
1. 在堆的现有大小中,每次插入的时间复杂度为O(log(k)),因此 .由于这些插入的常熟薪资(一半)在最大常数因子内,因此我们可以渐进地假设 ;形式上时间是 . 这也可以从斯特林公式中很容易看出。
2. 跳到:a b c d e f g h i 摊平时间
3. n是较大堆的大小。
4. 下界 上界
5. Brodal和Okasaki后来描述了一个具有相同边界的持久变体,除了reduce-key,这是不受支持的。 具有n个元素的堆可以在O(n)中自下而上构建。
堆数据结构有许多应用。
std.container.BinaryHeap
,它是根据D的范围实现的。实例可以从任意随机访问范围构建。二叉堆(BinaryHeap)公开了一个输入范围接口,该接口允许用D的内置foreach语句进行迭代,并与std.algorithm
包的基于范围的应用编程接口进行集成。^CORMEN, THOMAS H. (2009). INTRODUCTION TO ALGORITHMS. United States of America: The MIT Press Cambridge, Massachusetts London, England. pp. 151–152. ISBN 978-0-262-03384-8..
^Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348, doi:10.1145/512274.512284.
^The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappush.
^The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappop.
^The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heapreplace.
^Suchenek, Marek A. (2012), "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/FI-2012-751..
^Cormen, Thomas H. (英语:Thomas H. Cormen); Leiserson, Charles E. ; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.CS1 maint: Multiple names: authors list (link).
^Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874..
^Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2.
^Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58.
^Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing: 1463–1485. doi:10.1137/100785351..
^Brodal, G. S. L.; Lagogiannis, G.; Tarjan, R. E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. p. 1177. doi:10.1145/2213977.2214082. ISBN 9781450312455..
^Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1..
^Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214..
^Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0..
^Frederickson, Greg N. (1993), "An Optimal Algorithm for Selection in a Min-Heap", Information and Computation (PDF), 104 (2), Academic Press, pp. 197–214, doi:10.1006/inco.1993.1030.
暂无