编程珠玑 -- 关于堆
堆是这样一种数据结构，它首先是一棵二叉树，而且还是一棵完全二叉树；其次，对于最小堆，父节点的值小于子节点。
有两种特殊要求的二叉树，一种是完全二叉树，一种是满二叉树。完全二叉树添加叶子节点的时候，要求从左到右添加，所以如果左子树没有被填满，就不会把叶子结点添加到右子树上。满二叉树则要求一个节点要么有两个孩子，要么就没有孩子。他们的形状如下：
?
完全二叉树的性质使我们可以使用一个数组来表达一棵完全二叉树，因为叶子结点加入到树的位置是固定的，所以我们可以通过下标找到他的父节点或子节点（如果有的话）。令根的下标为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;}//其他操作//....};?