多條告白如次劇本只需引入一次

暫時這個系列的作品都挑著特殊典范的，讓人暫時一亮的算法，即日的堆排序算法即是個中一個。開始領會什么是堆，這內里堆（Heap）并不是步調中外存地區，而是一種實足二叉樹表白的數據構造。堆具備以次特性

是一個實足二叉樹堆的每個節點的值必需大于即是安排樹節點（大頂堆），或小于即是安排樹節點（小頂堆）。大略證明下，實足二叉樹是除去結果一層葉子節點外，其余的節點都有兩個子樹，而葉子節點不妨沒有子樹，大概惟有左子樹。如次圖即是個大頂堆：

小頂堆

堆保存

堆由于是實足二叉樹，特殊符合用數組保存，上海圖書館為大頂堆的保存情景，個中a[0]不必，a[1]為大頂堆的極點，也即是最大的數據，a[12]=7為左子樹極點，a[12+1]=6為右子樹的極點，其余節點情景順序類比。

堆的兩種操縱

向堆插入元素

用圖來表白如次：

向堆插入元素，先插入到結果一個數組元素場所，而后和本人的父節點6比擬，因為比6大不滿意大頂堆的前提，以是9和6調換，而后9再和堆頂元素8比擬，又不滿意大頂堆前提，連接調換，結果產生一個大頂堆，這個辦法叫堆化。

簡略堆頂元素

對于大頂堆來說，堆頂的元素為最大值，順序簡略堆頂元素并輸入，那么即是將數字從大向小陳設了。

這內里又個本領，即是簡略堆頂元素的功夫，不許徑直簡略，要用堆頂元素和結果一個元素做調換，而后按照堆的特性安排堆，直到滿意前提。

完備代碼如次：

packagecom.dianneng.lms;publicclassTestHeap{privateint[]a;privateintn;privateintcount;publicTestHeap(intcap){a=newint[cap+1];n=cap;count=0;}publicvoidswap(inti,intj){inttmp=a[i];a[i]=a[j];a[j]=tmp;return;}publicvoidprint(){for(inti=0;i<=count;i++){System.out.print(a[i]+"t");}}publicintinsert(intv){if(count==n){System.out.println("Heapisfull!");return-1;}else{a[++count]=v;inti=count;while(i/2>0&&a[i]>a[i/2]){swap(i,i/2);i=i/2;}}return0;}publicintremoveMax(){if(count==0){return-1;}System.out.print(a[1]+"t");a[1]=a[count];--count;heapify(count,1);return0;}privatevoidheapify(intn,inti){while(true){intmaxPos=i;//經過安排子樹極點比擬贏得最大數節點if(i*2<=n&&a[i]<a[i*2]){maxPos=i*2;}if(i*2+1<=n&&a[maxPos]<a[i*2+1]){maxPos=i*2+1;}//仍舊是最大的不必調換了if(maxPos==i){break;}//須要調換swap(i,maxPos);//i指向待調換的i=maxPos;}}publicstaticvoidmain(String[]args){TestHeapth=newTestHeap(18);th.insert(8);th.insert(7);th.insert(6);th.insert(5);th.insert(4);th.insert(3);th.print(