查看“︁二叉堆”︁的源代码

{{NoteTA
|G1 = IT
|1 = zh-cn:堆; zh-tw:堆積;
}}
{{Infobox data structure
|name=二叉堆
|type=二元樹／堆
|invented_by={{le|J·W·J·威廉斯|J. W. J. Williams}}
|invented_year=1964年
|space_avg=<math>O(n)</math>
|space_worst=<math>O(n)</math>
|search_avg=<math>O(n)</math>
|search_worst=<math>O(n)</math>
|insert_worst=<math>O(\log n)</math>
|insert_avg=<math>O(1)</math>
|delete_min_avg=<math>O(\log n)</math>
|delete_min_worst=<math>O(\log n)</math>
|find_min_avg=<math>O(1)</math>
|find_min_worst=<math>O(1)</math>
}}
'''二叉堆'''（{{lang-en|Binary heap}}）是一种特殊的[[堆 (数据结构)|堆]]，二叉堆是[[完全二叉树]]或者是近似完全二叉树。二叉堆满足堆特性：父節点的键值总是保持固定的序关系于任何一个子节点的键值，且每个節点的左子树和右子树都是一个二叉堆。

当父[[節点]]的键值总是大于或等于任何一个子节点的键值时为「最大堆」。当父節点的键值总是小于或等于任何一个子节点的键值时为「最小堆」。

== 存储 ==
二叉堆一般用[[数组]]来表示。如果根[[节点]]在数组中的位置是1，第''n''个位置的子节点分别在2''n''和 2''n''+1。因此，第1个位置的子节点在2和3，第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点。

如果存储数组的下标基于0，那么下标为i的节点的子节点是2''i'' + 1与2''i'' + 2；其父节点的下标是⌊''floor''((''i'' − 1) ∕ 2)⌋。[[函数]]''floor''(''x'')的功能是“向下取整”，或者说“向下舍入”，即取不大于''x''的最大整数（与“四舍五入”不同，向下取整是直接取按照数轴上最接近要求值的左边值，即不大于要求值的最大的那个值）。比如''floor''(1.1)、''floor''(1.9)都返回1。

如下图的两个堆：
             1                                 11                          
          /      \                          /      \ 
        2         3                       9         10
     /    \     /   \                   /   \     /    \ 
    4      5   6     7                5      6   7      8
   / \    / \                        / \    / \
  8  9   10 11                      1   2  3   4 

将这两个堆保存在以1开始的数组中：
 位置:  1  2  3  4  5  6  7  8  9 10 11
 左图:  1  2  3  4  5  6  7  8  9 10 11
 右图: 11  9 10  5  6  7  8  1  2  3  4

对于一个很大的堆，这种存储是低效的。因为节点的子节点很可能在另外一个内存页中。[[B-heap]]是一种效率更高的存储方式，把每个子树放到同一内存页。

如果用指针链表存储堆，那么需要能访问叶节点的方法。可以对二叉树“穿线”(threading)方式，来依序遍历这些节点。

== 基本操作 ==
在二叉堆上可以进行插入[[节点]]、删除节点、取出值最小的节点、减小节点的值等基本操作。

===插入节点===
在数组的最末尾插入新节点。然后自下而上调整子节点与父节点（称作up-heap或bubble-up, percolate-up, sift-up, trickle up, heapify-up, cascade-up操作）：比较当前节点与父节点，不满足「堆性质」则交换。从而使得当前子树满足二叉堆的性质。[[时间复杂度]]为<math>O(\log n)</math>。

===删除根节点===
删除根节点用于[[堆排序]]。

对于最大堆，删除根节点就是删除最大值；对于最小堆，是删除最小值。然后，把堆存储的最后那个节点移到填在根节点处。再从上而下调整父节点与它的子节点：对于最大堆，父节点如果小于具有最大值的子节点，则交换二者。这一操作称作down-heap或bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down,extract-min/max等。直至当前节点与它的子节点满足「堆性质」为止。

下属对最大堆的自上而下调整堆的[[伪代码]]中，数组A的下标索引值是从1开始：

'''Max-Heapify'''<ref name="CLRS">{{Citation | last1= Cormen | first1=T. H. | last2=al. | lastauthoramp=yes | title=Introduction to Algorithms | publisher=The MIT Press | place=Cambridge, Massachusetts | edition=2nd | year=2001 | isbn=0-07-013151-1}}</ref> (''A'', ''i''):<br/>
{{pad|2em}}''left'' ← 2''i''<br/>
{{pad|2em}}''right'' ← 2''i'' + 1<br/>
{{pad|2em}}''largest'' ← ''i''<br/>
{{pad|2em}}'''if''' ''left'' ≤ ''heap_length''[''A''] '''and''' ''A''[''left''] > A[''largest''] '''then''':<br/>
{{pad|4em}}''largest'' ← ''left''<br/>
{{pad|2em}}'''if''' ''right'' ≤ ''heap_length''[''A''] '''and''' ''A''[''right''] > ''A''[''largest''] '''then''':<br/>
{{pad|4em}}''largest'' ← ''right''<br/>
{{pad|2em}}'''if''' ''largest'' ≠ ''i'' '''then''':<br/>
{{pad|4em}}'''swap''' ''A[''i''] ↔ ''A''[''largest'']<br/>
{{pad|4em}}Max-Heapify(''A'', ''largest'')
===构造二叉堆===
一个直观办法是从单节点的二叉堆开始，每次插入一个节点。其时间复杂度为<math>O(n \log n)</math>。

最优算法是从一个节点元素任意放置的二叉树开始，自底向上对每一个子树执行删除根节点时的Max-Heapify算法（这是对最大堆而言）使得当前子树成为一个二叉堆。具体而言，假设高度为h的子树均已完成二叉堆化，那么对于高度为h+1的子树，把其根节点沿着最大子节点的分枝做调整，最多需要h步完成二叉堆化。可以证明，这个算法的时间复杂度为<math>O(n)</math>。

建造最大堆的伪代码：

'''Build-Max-Heap'''<ref name="CLRS"/> (''A''):<br/>
{{pad|2em}}''heap_length''[''A''] ← ''length''[''A'']<br/>
{{pad|2em}}'''for''' ''i'' ← ''floor''(''length''[''A'']/2) '''downto''' 1 '''do'''<br/>
{{pad|4em}}'''Max-Heapify'''(''A'', ''i'')

===合并两个二叉堆===
最优方法是把两个二叉堆首尾相连放在一个数组中，然后构造新的二叉堆。时间复杂度为<math>O(\log n \log k)</math>，其中n、k为两个堆的元素数目。

如果经常需要合并两个堆的操作，那么使用[[二项式堆]]更好，其时间复杂度为<math>O(\log n)</math>。

== 参见 ==
* [[最大—最小堆]]

== 参考文献 ==
{{Reflist}}

== 外部链接 ==
* [http://mathworld.wolfram.com/Heap.html http://mathworld.wolfram.com/Heap.html]{{Wayback|url=http://mathworld.wolfram.com/Heap.html |date=20200515004338 }}
* [https://web.archive.org/web/20040611075754/http://www.policyalmanac.org/games/binaryHeaps.htm https://web.archive.org/web/20040611075754/http://www.policyalmanac.org/games/binaryHeaps.htm]

{{计算机科学中的树}}

[[Category:树结构]]
[[Category:堆]]