堆(heap)的定义及其算法分析

堆(heap)是与二叉查找树类似的ADT。但又不同于二叉查找树，主要体现在两个方面。第一，可将二叉查找树看着是有序的，而堆是有序的，这一概念较弱。不过，为使优先队列操作有效执行，这完全满足要求。第二，二叉查找树有多种不同形状，而堆总是完全二叉树。
堆是完全二叉树，可以为空，或者：
（1）根包含的查找关键字大于或等于各个孩子的查找关键字。
（2）根包含作为子树的堆。
在这个堆的定义中，根项包含的查找关键字最大。这样的堆称为maxheap。相对而言，minheap将包含最小查找关键字的项放在根中。
堆是完全二叉树，因此，若了解堆的最大规模，则可以用二叉树的基于数组的实现。图1显示堆及其数组表示。堆节点中的查找关键字大于或等于节点的孩子的查找关键字。另外，在堆中，孩子的查找关键字相互无关：换言之，并不知道那个孩子包含的查找关键字更大。

图1 堆及数组表示形式

堆的基于数组的实现
* items ：堆项数组
* size ：表示堆中的项数的整数
数组items对应于树的基于数组的表示。在下面的讨论中，为简化起见，假设堆项是整数。
heapDelete
首先考虑heapDelete操作。堆中最大的查找关键字在什么位置？因为各个节点的查找关键字都大于或等于任意一个孩子的查找关键字，所以最大的查找关键字一定在树根中，这样，heapDelete操作的第1步为：
// return the item in the root
rootitem=item[0];
这很简单，但也必须删除根。再删除根后，将留下两个分离的堆，如图2-a所示。因此，需要将其余点在转化为一个堆。在开始转换的时候，取出树中最后一个节点的项，并将其放在根中，如下所示：
//copy the item from the last node into the root
item[0]=item[size-1];
//remove the last node
--size
如图2-b所示，给步骤的结果不一定是堆，不过，这是一棵完全二叉树，左右子树都是堆。唯一的问题是，根项可能不在正确的位置，这样的结构称为半堆（semiheap）。需要一种方式，将半堆转化为堆。一种策略是使根项逐渐下移，直到进入处于正确的位置的节点停止。为此，首先比较半堆根的查找关键字与孩子的查找关键字。如果根的查找关键字小于孩子的查找关键字中的比较大者，则交换根与较大孩子的项，所谓较大孩子，即查找关键字大于另一个孩子的查找关键字。

图2 （a）分离堆 （b）半堆
图3显示heapDelete操作。只做了一次交换，值5就下移至正确的位置：不过，一般情况都需要多次交换。实际上，一旦交换了根项和较大孩子C的项，C就成为半堆的根（注意，C并不移动，更改的是它的值）。该策略引出了下面的迭归算法。

图3 从堆中删除

heapRebuild(inout items :arrayType,in root :integer,
		in size :integer)
//Coverts a semiheap rooted at index root into a heap 
//Recursively trickle the item at index root down to 
//its proper position by swapping it with its larger child ,if the 
//child is larger than the item
//if the item is at a leaf ,nothing needs to be done
if(the root is not leaf)
{
	//root must hace a left child
	child=2*root+1;

	if(the root has a right child)
	{
		rightChild=child+1;
		if(items[rightChild].getKey()>items[child].getKey())
			child=rightChild;
	}
	//if the item in the root has a smaller search key
	//than the search key of the item in the larger
	//child,swap items
	if(items[root].getkey()<items[child].getkey())
	{
		swap items[root] and items[child]
		//transform semiheap rooted at child into a heap
		heapRebuild(items,child,size);
	}
}
//else root is a leaf ,so you are done

图4演示heapRebuild 的递归调用。

图4 heapRebuild的递归调用。
heapDelete操作使用heapRebuilt。如下所示：
//return the item from the last node into the root
rootItem=item[0];
//copy the item from the last node into the root
items[0]=items[size-1];
//remove the last node
--size;
//transform the semiheap back into a heap
heapRebuild(items,0,size);
简要分析heapDelete的效率。树存储在数组中，为删除节点，需要交换数组元素，而不是简单的修改几个指针。这些交换值得关注，但不意味着效率低下。最多交换数组元素多少次？在heapDelete将树中最后一个节点的项复制到根之后，heapRebuilt在树中下移此项，直到适当的位置，在最坏的情况下，项从根出发，沿单个路径下移，到达叶子。因此，heapRebuilt必须交换的数组项数不大于树的高度。包含n个节点的完全二叉树的高度为[log2(n+1)]（大于log2(n+1)的最小整数）。每个交换需要移动3次数据。因此，heapDelete需要的数据移动次数为3*[log2(n+1)]+1所以，heapDelete为O(log n),实际上，这非常有效。
heapInsert
heapInsert 算法的策略与heapDelete正好相反。在树低插入一个新项，然后上移到适当位置，如图5所示。上移节点很容易，因为items[i]（而不是根）节点总存储在items[(i-1)/2]中。heapInsert操作的伪码如下：

图5 在堆中插入

//insert newitem into the bootom of the tree
items[size]=newitem;
//trickle new item up to appropriate spot in the tree
place =size;
parent=(place-1)/2;
while(parent>=0 and (items[place]>items[parent]))
{
	Swap items[place] and items[parent]
	place=parent;
	parent=(place-1)/2;
}
Increment size

heapInsert的效率与heapDelete相同，换言之，在最坏的情况下，heapInset必须交换从叶子到根的路径上的数组元素。故交换次数不超过树高。完全二叉树的高度为[log2(n+1)],因此heapInsert也是O(log n)。