编程珠玑 -- 关于堆

堆是这样一种数据结构，它首先是一棵二叉树，而且还是一棵完全二叉树；其次，对于最小堆，父节点的值小于子节点。
有两种特殊要求的二叉树，一种是完全二叉树，一种是满二叉树。完全二叉树添加叶子节点的时候，要求从左到右添加，所以如果左子树没有被填满，就不会把叶子结点添加到右子树上。满二叉树则要求一个节点要么有两个孩子，要么就没有孩子。他们的形状如下：


 
完全二叉树的性质使我们可以使用一个数组来表达一棵完全二叉树，因为叶子结点加入到树的位置是固定的，所以我们可以通过下标找到他的父节点或子节点（如果有的话）。令根的下标为1，则对于节点i，其父结点下标为i/2,孩子节点下标分别为i*2和i*2+1.
堆有两个重要的操作，可以用于构建堆或维持堆的性质，他们分别为shiftup和shiftdown。shiftup(int n)操作的前提是数组X[1,n-1]满足堆的性质，经过该操作后，X[1,n]满足堆的性质。shiftdown（int n)操作的前提是数组X[2,n]满足堆的性质，经过该操作后X[1,n]满足堆的性质。关于shiftup，因为X[1,n-1]已经满足堆的性质，所以对于新加入的元素X[n]，只需要沿着其父节点往上交换，直到遇一个比他小的父节点或者直到他已经到了根节点的位置。与shiftup相反，shiftdown则将沿着孩子节点的方向往下交换，但是与shiftup不同的时，他这时候可能面临两个选择，只要父节点比他的孩子节点中比较小的孩子节点大，那么就将进行交换。它们的实现如下：

 

//precondition: heap[1,n-1]
//postcondition: heap[1,n]	
void Heap::siftup( int n ){
	int i=n;
	/*while( i>1 && array[i/2]>array[i] ){
		int t = array[i];
		array[i] = array[i/2];
		array[i/2] = t;
		i = i/2;
	}*/
	int hold = array[0];
	array[0] = array[n];		//这样将不用进行是否到达根的测试
	while( array[i/2]>array[i] ){
		int t = array[i];
		array[i] = array[i/2];
		array[i/2] = t;
		i = i/2;
	}
	array[0] = hold;
}

//precondition: heap[2,n]
//postcondition: heap[1,n]
void Heap::siftdown( int n ){
	int i=1, small=i;
	while( i<=n/2 ){
		small = i*2;
		if( small+1 <= n )
			if( array[small+1] < array[small] )
				small++;
		if( array[i] <= array[small] )
			break;
		int t = array[i];
		array[i] = array[small];
		array[small] = t;
		i = small;
	}
}

//这是对siftdown(n)的一点小改动
//它将用于堆的构建中
//precondition:heap[i+1,n]
//postcondition:heap[i,n]
void Heap::siftdown( int i, int n ){
	int small;
	while( i<=n/2 ){
		small = i*2;
		if( small+1 <= n )
			if( array[small+1]<array[small] )
				small++;
		if( array[i] <= array[small] )
			break;
		int t = array[i];
		array[i] = array[small];
		array[small] = t;
		i = small;
	}
}

 

堆的一个应用是优先堆，如优先权高的先被服务，他一般包含两个操作，一个是取当前优先级最高的元素，即根节点，取出根节点后，数组X[1,n]将不再满足堆的性质，但是数组X[2,n]的仍满足，可以通过把X[n]放到X[1]处从而达到shiftdown(n-1)的前提条件，从而维持堆的性质。另一个操作是插入一个新的元素，新加入的元素n破坏了整个数组的堆性质，但是满足shiftup(n)前提，通过shiftup来维持堆的性质。优先级堆的两个操作如下：

 

void insert( int t ){
	if( size == 0 ){
		array[++size] = t;
		return;
	}
	if( size<maxlen ){
		array[++size] = t;
		siftup(size);
	}
}
int extractMin(){
	int t = array[1];
	array[1] = array[size];
	array[size] = t;
	size --;
	siftdown( size );
	return array[size+1];
}

堆的另一个应用是排序。既然每取一次就得到第i小的值，那么对一个已经建好的有n个元素的堆经过n次取值，将得到一个排好序的数组。因此除了一个取当前最小值的操作外，排序还需要对数组X[1,n]进行建堆。可以通过两个方向来构造堆。一种是从根到叶节点，数组X[1,i]从i=1开始，通过shiftup(i+1)使X[1,i+i]满足堆的性质，最后建成堆X[1,n]。另一种从叶节点到根节点。因为叶子节点都没有孩子，他们满足堆的性质，然后从最后一个父节点开始往下shiftdown，由完全二叉树的性质，可以得到最后一个父节点为n/2。

void build(){
	for( int i=size/2; i>0; i-- )
		siftdown(i, size);
}

int sort(){
	for( int i=size; i>1; i-- ){
		int t = array[1];
		array[1] = array[i];
		array[i] = t;
		siftdown( i-1 );
	}
}

 优先级堆和用于排序的堆的初始化方法可能也不一样：

class Heap{
	private:
		int size, maxlen;
		int* array;		
	public:
		//优先级堆
		Heap( int len ){
			maxlen = len;
			size = 0;
			array = new int[maxlen+1];
		}
		//排序堆
		Heap( int* a, int len ){
			array = --a;
			size = len;
			maxlen = len;
		}
		//其他操作
		//....
	};