二叉堆
二叉堆
二叉堆（）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为「最大堆」。当父节点的键值总是小于或等于任何一个子节点的键值时为「最小堆」。
存储.
二叉堆一般用数组来表示。如果根节点在数组中的位置是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操作）：比较当前节点与父节点，不满足「堆性质」则交换。从而使得当前子树满足二叉堆的性质。时间复杂度为formula_1。
删除根节点.
删除根节点用于堆排序。
对于最大堆，删除根节点就是删除最大值；对于最小堆，是删除最小值。然后，把堆存储的最后那个节点移到填在根节点处。再从上而下调整父节点与它的子节点：对于最大堆，父节点如果小于具有最大值的子节点，则交换二者。这一操作称作down-heap或bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down,extract-min/max等。直至当前节点与它的子节点满足「堆性质」为止。
下属对最大堆的自上而下调整堆的伪代码中，数组A的下标索引值是从1开始：
Max-Heapify ("A", "i"):
"left" ← 2"i"
"right" ← 2"i" + 1
"largest" ← "i"
if "left" ≤ "heap_length"["A"] and "A"["left"] > A["largest"] then:
"largest" ← "left"
if "right" ≤ "heap_length"["A"] and "A"["right"] > "A"["largest"] then:
"largest" ← "right"
if "largest" ≠ "i" then:
swap "A["i"] ↔ "A"["largest"]
Max-Heapify("A", "largest")
构造二叉堆.
一个直观办法是从单节点的二叉堆开始，每次插入一个节点。其时间复杂度为formula_2。
最优算法是从一个节点元素任意放置的二叉树开始，自底向上对每一个子树执行删除根节点时的Max-Heapify算法（这是对最大堆而言）使得当前子树成为一个二叉堆。具体而言，假设高度为h的子树均已完成二叉堆化，那么对于高度为h+1的子树，把其根节点沿着最大子节点的分枝做调整，最多需要h步完成二叉堆化。可以证明，这个算法的时间复杂度为formula_3。
建造最大堆的伪代码：
Build-Max-Heap ("A"):
"heap_length"["A"] ← "length"["A"]
for "i" ← "floor"("length"["A"]/2) downto 1 do
Max-Heapify("A", "i")
合并两个二叉堆.
最优方法是把两个二叉堆首尾相连放在一个数组中，然后构造新的二叉堆。时间复杂度为formula_4，其中n、k为两个堆的元素数目。
如果经常需要合并两个堆的操作，那么使用二项式堆更好，其时间复杂度为formula_1。
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.