二叉堆

二叉堆是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父節点的键值总是大于或等于（小于或等于）任何一个子节点的键值，且每个節点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

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

存储

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

如下图的两个堆：

        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

基本操作

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

参见

• 最大/最小堆

外部链接

• http://mathworld.wolfram.com/Heap.html
• http://www.policyalmanac.org/games/binaryHeaps.htm