堆

定义：一个大小为n的堆是一棵包含n个结点的完全二叉树，该树中每个结点的关键字值大于等于其双亲结点的关键字值。完全二叉树的根称为堆顶，它的关键字值是整棵树上最小的。这样定义的堆称为最小堆 。

类似地，还可以定义最大堆 。

向下调整

    void AdjustDown (T heap[], int r,int j)

    设 （heap[r+1],…,heap[j]） 这j-r个位置上的元素已满足特性：heap[i]<=heap[2i+1] 且heap[i]<=heap[2i+2] 的条件，运行此函数将使得增加一个元素heap[r]，(heap[r], heap[r+1],…,heap[j]) 这j-r+1个元素也满足堆的特性。

图示：

代码实现：

template <class T>
void AdjustDown (T heap[], int r, int j)
{    //下标从r+1到j已满足堆的条件
   int child=2*r+1;                                  //左孩子
   T temp=heap[r]; 
   while  (child<=j) {
        if (( child <j) && ( heap[child]>heap[child+1])) child++;
        if  (temp<=heap[child]) break;
        heap[(child-1)/2]=heap[child];
        child=2*child+1;
   }
   heap[(child-1)/2]=temp;
}
template <class T> 
void CreateHeap(T heap[],int n)
{
       for (int i=(n-2)/2;i>-1;i--) 
                       AdjustDown(heap,i,n-1)；
}