二叉堆是優(yōu)先隊列很普遍的一種實現(xiàn)，它又分為最小堆最大堆，最小堆和最大堆都是完全二叉樹。
其結(jié)構(gòu)體定義如下：

struct HeapStruct {
    int Capacity;    //堆的最大容量
    int Size;         //堆的當前結(jié)點數(shù)
    ElementType *Elements;   //存放堆結(jié)點的數(shù)組
}

typedef struct HeapStruct *PriorityQueue;

二叉堆的結(jié)點可以保存在一個數(shù)組中。
1、如果從數(shù)組的索引1開始存放堆結(jié)點，那么對于數(shù)組中任意位置i上的元素，其左兒子在位置2i上，右兒子在左兒子后的單元(2i + 1)中
2、如果從數(shù)組的索引0開始存放堆結(jié)點，那么對于數(shù)組中任意位置i上的元素，其左兒子在位置(2i+1)上，右兒子在左兒子后的單元(2i+2)中。

在下面的代碼中，統(tǒng)一采用第一種方式存放堆結(jié)點。你可以通過下面的代碼注意到，用第一種方式給編程帶來的好處。

最小堆：父結(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值。

（1）插入操作Insert，采用制造“空穴”，上濾的方式——“空穴”在堆中不斷上移直到找出正確的位置。插入操作復雜度O(logN)。

void Insert(ElementType X, PriorityQueue H) {
    int i;

    if( IsFull(H) ) {      //判斷堆是否已滿
        Error( "Priority queue is full" );
        return ;
    }

    for( i = ++ H->Size; H->Elements[i/2] > X; i = i/2) {
        H->Elements[i] = H->Elements[i/2] ; 
    }
    H->Elements[i] = X ;
}

（2）刪除最小元素(即根?結(jié)點)DeleteMin，下濾的方式。刪除最小元素操作的復雜度O(logN)，因為刪除后涉及重建堆。

ElementType DeleteMin(PriorityQueue H) {
    int i, Child ;
    ElementType MinElement, LastElement;

    if( IsEmpty(H) ) {        //判斷堆是否為空
        Error( "Priority queue is empty" );
        return H->Elements[0];
    }
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--]; //在?根結(jié)點刪除了第一個堆結(jié)點，因此在根結(jié)點制造了一個“空穴”，
先保存最后一個堆結(jié)點，堆大小減1。下面的?代碼是把LastElement放到合適的地方。

    for( i =1; i*2 <= H->Size; i= Child) {  //下濾過程
        
        //找較小的一個兒子結(jié)點
        Child = i * 2;            //左兒子結(jié)點
        if(Child != H->Size && H->Elements[Child + 1] < H->Elements[Child] )
            Child++;               //如果左兒子不是新堆的最后一個結(jié)點，且左兒子大于右兒子，我們選擇右兒子
        
        //判斷較小的兒子結(jié)點是否小于LastElement。若是，把該較小的兒子結(jié)點上移到自己的父結(jié)點；
        //若不是，退出循環(huán)。（即LastElement比兒子結(jié)點都小，可以作為它們的父結(jié)點插入）
        if(LastElement > H->Elements[Child] ) 
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement ; 
    return MinElement;    //返回被刪除的根節(jié)點
}

（3）如果僅僅是?要獲得最小值，那么可以在常數(shù)時間完成O(1)。

</br>

最大堆：父結(jié)點的鍵值總是?大于或等于任何一個子節(jié)點的鍵值。

（1）插入操作Insert，采用制造“空穴”，上濾的方式——“空穴”在堆中不斷上移直到找出正確的位置。插入操作復雜度O(logN)。

void Insert(ElementType X, PriorityQueue H) {
    int i ;
    
    if( IsFull(H) ) {
        Error( "Priority queue is full" );
        return ;
    }

    for(i=++H->Size; H->Elements[i/2] < X; i = i/2) {
        H->Elements[i] = H->Elements[i/2];
    }
    H->Elements[i] = X;
}

對比最小堆的插入操作，可看到只是把for循環(huán)的條件">X"改為"<X"。意思是只要X比它的父結(jié)點大，就一直上濾。

（2）刪除最大元素(即根?結(jié)點)DeleteMax，下濾的方式。刪除最大元素操作的復雜度O(logN)，因為刪除后涉及重建堆。

ElementType DeleteMax(PriorityQueue H) {
    int i, Child;
    ElementType MaxElement, LastElement;

    if( IsEmpty(H) ) {
        Error( "Priority queue is empty" );
        return H->Elements[0];
    }

    MaxElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];

    for(i=1; 2*i <=H-Size; i = Child) {
        Child = i*2;
*        if(Child != H->Size && H->Elements[Child+1] > H->Elements[Child])
            Child++;

*        if(LastElement < H->Elements[Child] )
            H->Elements[i] = H->Elements[Child];
        else
            break;
    } 
    H->Elements[i] = LastElement;
    return MaxElement;
}

與最小堆的刪除最小元素操作相比，有2處條件判斷發(fā)生改變，已用*號標出，讀者可以自行體會。
（3）如果僅僅是要獲得最大值，那么可以在常數(shù)時間完成O(1)。

</br>

二叉堆的應用——堆排序：

用最大堆完成堆排序，每次DeleteMax花費時間O(logN)，對N個元素進行排序就是O(NlogN)。
另外建立二叉堆花費的時間為O(N)。不解可參考->《為什么堆排序構(gòu)建堆的時間復雜度是N》
所以堆排序的時間復雜度為O(NlogN)+O(N) = O(NlogN)，因為是就地排序，所以空間復雜度為O(1)。

void HeapAdjust(int *a, int i, int size) {   //調(diào)整堆
    int Child;
    int tmp;
    
    for(tmp = a[i]; 2*i+1 < size; i = Child) {
        Child = 2*i+1;   //左兒子
        if(Child != size-1 && a[Child+1] > a[Child])   //如果右兒子比左兒子大，取右兒子
            Child++;
    
        if(tmp < a[Child])
            a[i] = a[Child];
        else
          break;
    }
    a[i] = tmp;
}

void HeapSort(int *a, int size) {    //堆排序主例程
    int i;
    for(i = size/2; i>=0; i--) {    //構(gòu)建堆
        HeapAdjust(a, i, size);
    }

    for(i = size-1; i>0; i--) {
        int temp = a[i];   //交換堆頂和最后一個元素，即每次將剩余元素中的最大者放到最后面 
        a[i] = a[0];
        a[0] = temp;
        HeapAdjust(a, 0, i);  //重新調(diào)整堆頂節(jié)點成為大頂堆
    }
    
}

注：堆排序代碼的堆結(jié)點從數(shù)組索引0開始