package DataStructure.mianshi; public class HeapSort { private int[] items; private int N; public HeapSort(int capacity){ items=new int[capacity+1]; N=0; } private boolean less(int i,int j){ return items[i]1){//如果到根节点则退出 if(less(k/2,k)){//如果父节点小则交换 因为是大顶堆 exch(k/2,k); k=k/2; }else{ break;//优化比较次数 } } } public void down(int k){ while(k*2<=N){//如果是叶子结点(最后一层) //找到子节点中较大值 int max; if(2*k+1<=N){//存在右子节点 if(less(2*k,2*k+1)){ max=2*k+1; }else{ max=2*k; } }else{//不存在右子节点 max=2*k; } //比较当前结点和子节点的较大者,如果当前结点不小,则结束循环 if(!less(k,max)){ break; } //当前结点小则交换 exch(k,max); k=max; } } } class test{ public static void main(String[] args) { HeapSort h=new HeapSort(6); h.insert(5); h.insert(6); h.insert(1); h.insert(4); h.insert(9); h.insert(7); for(int i=0;i<6;i++){ System.out.println(h.delMax()); } } }