多条告白如次剧本只需引入一次
暂时这个系列的作品都挑着特殊典范的，让人暂时一亮的算法，即日的堆排序算法即是个中一个。开始领会什么是堆，这内里堆（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(
