????上篇文章數(shù)據(jù)結(jié)構(gòu)之二叉堆(優(yōu)先隊列)——原理解析詳細(xì)介紹了二叉堆的實現(xiàn)原理，本篇文章在上篇文章的基礎(chǔ)上，介紹二叉堆的建堆原理，二叉堆的入隊和出隊操作的java代碼實現(xiàn)。

一丶二叉堆的存儲結(jié)構(gòu)

????在上篇文章中，為了清晰的介紹二叉堆的原理，我們將二叉堆畫出成了鏈?zhǔn)浇Y(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)涉及比較多的指針操作，因為二叉堆的具有完全二叉樹的結(jié)構(gòu)特性，更為簡單的做法是將二叉堆的存儲結(jié)構(gòu)設(shè)計為數(shù)組。

圖1 大根堆

圖2 存儲結(jié)構(gòu)

• 利用數(shù)組來存數(shù)大根堆其存儲順序和樹的層次遍歷順序相同
• 數(shù)組的第一個元素(下標(biāo)Index=0)不存放數(shù)據(jù)，重當(dāng)哨兵元素，其具體作用后續(xù)會涉及。
• 在二根堆不斷的入隊和出隊的操作下，數(shù)組中元素的數(shù)目會發(fā)生變化，必須設(shè)置一個指針，指向數(shù)組的邊界元素。
• 二叉堆是具有堆序的完全二叉樹，那么也滿足完全二叉樹的所有特點，可以知道對于完全二叉樹的數(shù)組存儲具有如下特點，對于數(shù)組中下標(biāo)為i的元素，若其左孩子存在，那么其左孩子下標(biāo)為2i，其右孩子若存在，下為2i+1，其父節(jié)點的坐標(biāo)為i/2。這是一條非常重要的性質(zhì)。

二丶二叉堆的建堆原理。

????對于N個元素的建堆的過程等價于N個元素插入的過程，這是對二叉堆建堆過程最直觀的理解，這里描述另外的一種方法。假如待建堆的數(shù)組如下，構(gòu)建一個大根堆。

A={5,9,4,3,2,1}

1. 依據(jù)待建堆數(shù)組構(gòu)建一個隨機(jī)完全二叉樹，構(gòu)建結(jié)果如下：

   
   
   圖3 隨機(jī)完全二叉樹

2. 對于圖3而言，已經(jīng)滿足了二叉樹的結(jié)構(gòu)特性了，只要完成二叉樹的堆序特性，那么建堆的過程就算完成了。此時二叉樹currentSize = 6，6這個下標(biāo)指向堆尾元素1。i=currentSize/2=3,3這個下標(biāo)指向堆尾元素1的父節(jié)點4，元素4也是最后一個非葉子節(jié)點。我們我們利用”下濾”操作調(diào)整元素4的堆序特性。結(jié)果如下圖，其實元素4滿足堆序特點，無需調(diào)整。

   
   
   圖4 第一次下濾調(diào)整

3. 步驟2中i=3，指向元素4，此時i--，i=2指向元素9，繼續(xù)利用下濾操作調(diào)整元素9的堆序特性結(jié)果如下：

   
   
   圖5 第二次堆序調(diào)整

4. i繼續(xù)自減，i=2，指向元素5，此時利用”下濾”操作調(diào)整該元素的堆序特性，調(diào)整如下：

   
   
   圖3第三次堆序調(diào)整
5. i繼續(xù)自減，i=0發(fā)現(xiàn)數(shù)組已無元素可調(diào)，結(jié)束，建堆完成。

三丶二叉堆的java代碼實現(xiàn)

//二叉堆--大根堆的java代碼實現(xiàn)
//利用二叉堆完全樹的結(jié)構(gòu)特性我們利用數(shù)組來存儲二叉堆。
public class BinaryHeap {
    //currentSize數(shù)組的邊界
    intcurrentSize;
    //儲存二叉堆節(jié)點元素的數(shù)組
    int[] item;
    publicBinaryHeap(int [] data){
       this.currentSize=data.length;
       //實際上并不是乘5,這里乘5只是為了保證其具有足夠的空間大小。
       item = new int[(currentSize+1)*5];
       //這里特別注意，數(shù)組的第一個元素并不存數(shù)數(shù)據(jù)
       //直接復(fù)制構(gòu)建一棵隨機(jī)完全二叉樹
       for(int i =0;i<data.length;i++){
           item[i+1] = data[i];
       }
       //對構(gòu)成的隨機(jī)完全二叉樹進(jìn)行堆序的調(diào)整
       buildHeap();
    }
    //建堆操作的原理：對隨機(jī)完全二叉樹的每個非葉子節(jié)點完成下濾操作。
    privatevoid buildHeap(){
       if(item==null||item.length<=0){
           return ;
       }
       for(int i =currentSize/2;i>0;i--){
           percolateDown(i);                      
       }
    }
    //index:指定下濾的元素下標(biāo)
    privatevoid percolateDown(int index) {
       intcopy = item[index];
       intchild=0;
       for(int i = index;i*2<=currentSize;i=child){
           //child指向左節(jié)點。
           child = i*2;
           //這需要判斷該節(jié)點是否存在右孩子
           int max = item[child];
           if(child+1<=currentSize&&max<item[child+1]){
              //++child指向右節(jié)點
              max = item[++child];
           }
           if(copy<max){
              //不滿足堆序性質(zhì)，覆蓋
              item[index] = max;
           }else{
              //滿足堆序性質(zhì)，結(jié)束該次堆調(diào)整。
              item[i] = copy;
              return ;
           }
       }
    }
    @Override
    publicString toString() {
       return"BinaryHeap [item=" + Arrays.toString(item) + "]";
    }
    publicvoid insert(int element){
       currentSize++;
       item[currentSize] = element;
       //數(shù)組元素0這里有個哨兵。
       item[0] = element;
       intparent = 0;
       for(int i = currentSize;i>0;i =parent){
            parent = i/2;
            if(item[parent]<item[0]){
               item[i] = item[parent];
            }else{
               item[i] = item[0];
               item[0] = 0;
               return;
            }
       }
    }
    publicint deleteMax(){
       intdata = item[1];
       item[1] = item[currentSize--];
       percolateDown(1);
       returndata;
    }
    publicstatic void main(String [] args){
       int[] data = new int[]{5,9,4,3,2,1};
       BinaryHeap heap = new BinaryHeap(data);
       heap.insert(10);
       System.out.println(heap.toString());
       System.out.println(heap.deleteMax());
       System.out.println("-----------------------");
       System.out.println(heap);
    }
}