堆（综述）

                     

贡献者： 待更新

　　 （本文根据 CC-BY-SA 协议转载自原搜狗科学百科对英文维基百科的翻译）

图
图 1：二叉堆的示例，其中节点为 1 到 100 之间的整数。

　　 在计算机科学中，堆是一种特殊的基于树的数据结构，本质上是一棵几乎完全的[1]树，它满足堆属性：在最大堆中，对于任意给定的节点 C，如果 P 是 C 的父节点，那么 P 的键（值）大于或等于 C 的键。在最小堆中，P 的键小于或等于 C 的键。堆 “顶部” 的节点（没有父节点）称为根节点。

　　 堆是称为优先队列的抽象数据类型的最有效实现，事实上优先队列通常被称为 “堆”，不管它们是如何实现的。在堆中，最高（或最低）优先级的元素总是存储在根节点。然而，堆不是排序结构，它可以被认为是部分有序的。当需要重复移除优先级最高（或最低）的对象时，堆是一种有用的数据结构。

　　 堆的一个常见实现是二叉堆，其中树是二叉树（见图）。堆数据结构，特别是二叉堆，是由 J. W. J. Williams 在 1964 年引入的，作为堆排序算法的数据结构。[2] 堆在一些高效的图算法中也很重要，比如 Dijkstra 算法。当堆是一棵完全二叉树时，它有一个最小的可能高度——一个有 N 个节点的堆，对于每个节点，一个分支总是有 loga N 的高度。

　　 注意，如图所示，兄弟和堂兄弟之间没有隐含的排序，也没有有序遍历的隐含序列（例如，在二叉搜索树中）。上面提到的堆关系仅适用于节点和它们的父亲、祖父等之间。每个节点可以拥有的最大子节点数取决于堆的类型。

1. 操作

　　 涉及堆的常见操作有:

　　 基础

　　 创建

　　 检查

　　 内部的

2. 实现

图
图 2：一个完全二叉最大堆的例子，节点是从 1 到 100 之间的整数。图示了它将如何存储在数组中。

　　 堆通常在数组(固定大小或动态数组)中实现，并且不需要元素之间的指针。元素插入堆或从堆中删除后，可能会违反堆性质，必须通过内部操作来平衡堆。

　　 二叉堆可以用单独使用数组的非常节省空间的方式来表示。第一个(或最后一个)元素将包含根元素。数组接下来两个元素包含根元素的孩子。接下来的四个包含两个子节点的四个子节点，等等。因此，在位置 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] 这比连续插入原始空堆的序列更快，该操作是对数线性的。

3. 变体

4. 变体理论界限的比较

　　 以下是各种堆数据结构的时间复杂度。函数名假设一个最小堆。

　　 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.

图
图 3
  1. Each insertion takes $O( \log\left(k\right) )$ in the existing size of the heap, thus $$\sum_{k=1}^N O(\log k).~$$ Since $$\log \frac{n}{2} = (\log n) - 1,~$$ a constant factor (half) of these insertions are within a constant factor of the maximum, so asymptotically we can assume $k = n$; formally the time is $$ n O(\log n) - O(n) = O(n \log n).~$$ This can also be readily seen from Stirling's approximation.
  2. Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with $n$ elements can be constructed bottom-up in $O(n)$.
  3. Amortized time.
  4. Lower bound of $\Omega(\log \log n)$, upper bound of $O(2^{2\sqrt{\log \log n}})$.
  5. $n$ is the size of the larger heap.
  1. 在堆的现有大小中，每次插入的时间复杂度为 $O(\ \log\left(k\right) )$，因此由于这些插入的常数薪资（一半）在最大常数因子内，因此我们可以渐进地假设；形式上的时间是。这也可以从弗斯特林公式中很容易看出。
  2. 跳到：$a b c d e f g h i$ 摆平时间
  3. $n$ 是较大堆的大小。
  4. 下界 上界
  5. Brodal 和 Okasaki 后来描述了一个具有相同边界的持久变体，除了 reduce-key，这是不受支持的。具有 $n$ 个元素的堆可以在 $O(n)$ 中自下而上地构建。

5. 应用

　　 堆数据结构有许多应用。

6. 实现_F

7. 参考文献

　　 [1] ^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..

　　 [2] ^Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348, doi:10.1145/512274.512284.

　　 [3] ^The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappush.

　　 [4] ^The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappop.

　　 [5] ^The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heapreplace.

　　 [6] ^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..

　　 [7] ^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).

　　 [8] ^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..

　　 [9] ^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.

　　 [10] ^Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58.

　　 [11] ^Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing: 1463–1485. doi:10.1137/100785351..

　　 [12] ^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..

　　 [13] ^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..

　　 [14] ^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..

　　 [15] ^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..

　　 [16] ^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.

                     

© 小时科技 保留一切权利