堆排序和合并排序一樣，是一種時(shí)間復(fù)雜度為O(nlgn)的算法，同時(shí)和插入排序一樣，是一種就地排序算法(不需要額外的存儲空間)。堆排序需要用到一種被稱為最大堆的數(shù)據(jù)結(jié)構(gòu)，與java或者lisp的gc不一樣，這里的堆是一種數(shù)據(jù)結(jié)構(gòu)，他可以被視為一種完全二叉樹，即樹里面除了最后一層其他層都是填滿的。也正是因?yàn)檫@樣，樹里面每個(gè)節(jié)點(diǎn)的子女和雙親節(jié)點(diǎn)的序號都可以根據(jù)當(dāng)前節(jié)點(diǎn)的序號直接求出。
Parent(i)=i/2
Left(i)=2*i
Right(i)=2*i+1
如上圖所示，1位置的子女節(jié)點(diǎn)分別為2,3 2節(jié)點(diǎn)的子女節(jié)點(diǎn)為4,5 2的雙親節(jié)點(diǎn)為1 考察其他節(jié)點(diǎn)也很容易發(fā)現(xiàn)上述關(guān)系。最大堆是一種特殊的堆，其特點(diǎn)是每個(gè)雙親節(jié)點(diǎn)的值都比子女節(jié)點(diǎn)大。他的這一特點(diǎn)使得他可以實(shí)現(xiàn)nlgn的就地排序?，F(xiàn)在我們先來看看怎么構(gòu)建和保持一個(gè)最大堆。
我們現(xiàn)在有一個(gè)數(shù)組A,大小是n，假設(shè)其中元素按照完全二叉樹的方式排列。如何將其構(gòu)造成一個(gè)最大堆？首先我們知道最大堆的每個(gè)子樹都符合最大堆的性質(zhì)（根節(jié)點(diǎn)值大于所有子節(jié)點(diǎn)）。同時(shí)我們知道序號為（n/2+1）~n的元素都是葉子節(jié)點(diǎn)（因?yàn)槠渥优?jié)點(diǎn)的序號都大于n，即說明沒有子女節(jié)點(diǎn)），因此我們構(gòu)建最大堆的操作就在序號為1~n/2的元素內(nèi)進(jìn)行（其他元素已滿足最大堆性質(zhì)）。我們定義如下操作maxify(i):將以i位置節(jié)點(diǎn)為根的子樹改造成最大堆。其操作內(nèi)容如下：對于每個(gè)節(jié)點(diǎn)i，我們考察他與子女節(jié)點(diǎn)的大小，如果他比某個(gè)子女節(jié)點(diǎn)小，則將他與子女節(jié)點(diǎn)中最大的那個(gè)互換位置，然后在相應(yīng)的子女節(jié)點(diǎn)位置重復(fù)操作，直到到達(dá)堆的葉子節(jié)點(diǎn)或者考察的位置比子女節(jié)點(diǎn)的值都要大為止。由此可知我們構(gòu)造最大堆buildmaxheap的過程就是在每個(gè)內(nèi)部節(jié)點(diǎn)上調(diào)用maxify過程，依次到樹的根部，此時(shí)其左右子樹都是最大堆，現(xiàn)在在根節(jié)點(diǎn)調(diào)用maxify即完成了最大堆的構(gòu)造。
有了最大堆的基礎(chǔ)結(jié)構(gòu)后，我們就可以利用最大堆的性質(zhì)進(jìn)行排序HeapSort，我們從根節(jié)點(diǎn)開始操作，因?yàn)楦?jié)點(diǎn)是這個(gè)數(shù)組中最大的元素，因此我們將其于數(shù)組中最后一個(gè)元素對換（排序后，最大元素應(yīng)該在最后）將heapsize減1，然后再在根節(jié)點(diǎn)出調(diào)用maxify過程將新的堆重新最大堆化。依次循環(huán)，我們每次都能將現(xiàn)有堆中最大的元素放到堆末尾。最后就完成了整個(gè)排序過程。操作情況見下圖（只列出了前4步）
public class MaxHeap {int[] heap;int heapsize;public MaxHeap(int[] array){ this.heap=array; this.heapsize=heap.length;}public void BuildMaxHeap(){ for(int i=heapsize/2-1;i>=0;i--) { Maxify(i);//依次向上將當(dāng)前子樹最大堆化 }}public void HeapSort(){ for(int i=0;i<heap.length;i++) { //執(zhí)行n次，將每個(gè)當(dāng)前最大的值放到堆末尾 int tmp=heap[0]; heap[0]=heap[heapsize-1]; heap[heapsize-1]=tmp; heapsize--; Maxify(0); }}public void Maxify(int i){ int l=Left(i); int r=Right(i); int largest; if(l<heapsize&&heap[l]>heap[i]) largest=l; else largest=i; if(r<heapsize&&heap[r]>heap[largest]) largest=r; if(largest==i||largest>=heapsize)//如果largest等于i說明i是最大元素 largest超出heap范圍說明不存在比i節(jié)點(diǎn)大的子女 return ; int tmp=heap[i];//交換i與largest對應(yīng)的元素位置，在largest位置遞歸調(diào)用maxify heap[i]=heap[largest]; heap[largest]=tmp; Maxify(largest);}public void IncreaseValue(int i,int val){ heap[i]=val; if(i>=heapsize||i<=0||heap[i]>=val) return; int p=Parent(i); if(heap[p]>=val) return; heap[i]=heap[p]; IncreaseValue(p, val);}private int Parent(int i){ return (i-1)/2;}private int Left(int i){ return 2*(i+1)-1;}private int Right(int i){ return 2*(i+1);}}
public class Demo {public static void main(String[] args){ int[] array=new int[]{1,2,3,4,7,8,9,10,14,16}; MaxHeap heap=new MaxHeap(array); System.out.println("執(zhí)行最大堆化前堆的結(jié)構(gòu)："); printHeapTree(heap.heap); heap.BuildMaxHeap(); System.out.println("執(zhí)行最大堆化后堆的結(jié)構(gòu)："); printHeapTree(heap.heap); heap.HeapSort(); System.out.println("執(zhí)行堆排序后數(shù)組的內(nèi)容"); printHeap(heap.heap); }private static void printHeapTree(int[] array){ for(int i=1;i<array.length;i=i*2) { for(int k=i-1;k<2*(i)-1&&k<array.length;k++) { System.out.print(array[k]+" "); } System.out.println(); } }private static void printHeap(int[] array){ for(int i=0;i<array.length;i++) { System.out.print(array[i]+" "); }}}
