堆（Heap）

1 int heap[MAX_SIZE];

 1 void DownAdjust(int low, int high)
 2 {
 3     int i=low, j=i*2;
 4     while(j <= high)
 5     {
 6         if(j+1<=high && heap[j+1]>heap[j])　　　//先比较左右孩子的大小
 7             j = j + 1;
 8         if(heap[j] > heap[i])　　　　//孩子大于父亲，则交换（大根堆）
 9         {
10             swap(heap[j], heap[i]);
11             i = j;　　　　//不断向下调整直至叶子结点
12             j = i * 2;　　
13         }
14         else
15             break;
16     }
17 }

1 void CreateHeap()
2 {  
3     for(int i=n/2; i>=1; i--)　　//从最后一个非叶子结点开始，直至根结点            
4     DownAdjust(i, n);       //依次向下调整
5 } 

1 void DeleteTop()
2 {
3     heap[1] = heap[n--];    //最后一个元素替代堆顶
4     DownAdjust(1,n);        //向下调整堆顶元素
5 }

void UpAdjust(int low, int high)
{
    int i=high, j=i/2;
    while(j>=low)
    {
        if(heap[j] < heap[i])　　//孩子大于父亲，则交换（大根堆）
        {
            swap(heap[j], heap[i]);
            i = j;
            j /= 2;
        }
        else
            break;
    }
}

1 void Insert(int x)
2 {
3     heap[++n] = x;　　//末尾插入结点
4     UpAdjust(1,n);　　//向上调整
5 }

1 void HeapSort()
2 {
3     CreateHeap();
4     for(int i=n; i>1; i--)
5     {
6         swap(heap[i], heap[1]);
7         DownAdjust(1,i-1);
8     }
9 }