數據結構與演算法：堆排序

05-08

堆排序是一種樹形選擇排序方法，它的特點是：在排序的過程中，將array[0，...，n-1]看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親節點和孩子結點之間的內在關係，在當前無序區中選擇關鍵字最大（最小）的元素。

在介紹對排序之前。我們先來介紹大根堆和小根堆。

1.創建二叉樹

若array[0，...，n-1]表示一顆完全二叉樹的順序存儲模式，則雙親節點指針和孩子結點指針之間的內在關係如下：

　　任意一節點指針 i：父節點：i==0 ? null : (i-1)/2

　　　　　　　　　　左孩子：2*i + 1

　　　　　　　　　　右孩子：2*i + 2

2.大根堆和小根堆的定義

n個關鍵字序列array[0，...，n-1]，當且僅當滿足下列要求：(0 <= i <= (n-1)/2)

　　　　　　① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]；稱為小根堆；

　　　　　　② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]；稱為大根堆；

3. 建立大根堆（後續建立代碼，對二叉樹建立不了解可以看前面寫的二叉樹創建的博客）：

　　n個節點的完全二叉樹array[0，...，n-1]，最後一個節點n-1是第(n-1-1)/2個節點的孩子。對第(n-1-1)/2個節點為根的子樹調整，使該子樹稱為堆。

　　對於大根堆，調整方法為：若【根節點的關鍵字】小於【左右子女中關鍵字較大者】，則交換。（需要注意的是二叉樹最後一個根節點可能沒有右孩子）

　　之後向前依次對各節點（(n-2)/2 - 1）~ 0為根的子樹進行調整，看該節點值是否大於其左右子節點的值，若不是，將左右子節點中較大值與之交換，交換後可能會破壞下一級堆，於是繼續採用上述方法構建下一級的堆，直到以該節點為根的子樹構成堆為止。

　　反覆利用上述調整堆的方法建堆，直到根節點。

4.堆排序：（大根堆）

　　①將存放在array[0，...，n-1]中的n個元素建成初始堆；

　　②將堆頂元素與堆底元素進行交換，則序列的最大值即已放到正確的位置；

　　③但此時堆被破壞，將堆頂元素向下調整使其繼續保持大根堆的性質，再重複第②③步，直到堆中僅剩下一個元素為止。

堆排序演算法的性能分析：

　　空間複雜度:o(1)；

　　時間複雜度:建堆：o(n)，每次調整o(log n)，故最好、最壞、平均情況下：o(n*logn);

　　穩定性：不穩定

我們下來來利用大根堆進行排序。（小根堆也是一樣的原理）

創建大根堆：

//創建大根堆 public static int[] buildMaxHeap(int[] arr){ //從最後一個父節點開始 for(int i=arr.length/2-1;i>=0;i--){ adjustDownToTop(arr,i,arr.length); } return arr; } public static void adjustDownToTop(int[] arr,int k,int length){ //提取該父節點的值存入temp中 int temp=arr[k]; //初始化k節點的左孩子節點為i for(int i=2*k+1;i<=length-1;i=2*i+1){ //選取值最大的子節點的下標(注意該節點可能沒有右子節點，所以判斷條件為i+1<length.不能等於) if(i+1<length&&arr[i]<arr[i+1]){ //如果右節點值大於左節點 i++; } //如果比父節點打，和父節點交換位置 if(arr[i]<=temp){ break; }else{ arr[k]=arr[i]; k=i;//用於最後的賦值 } } arr[k]=temp; }

然後進行堆排序：

思想：創建大根堆之後，第一個元素是最大的，那麼我們將其和堆的最後一個元素交換。

然後重新調整堆結構。這次調整堆結構的length為length-1,每次提取出一個元素都重新調整堆結構，長度-1。

//堆排序 public static void heapSort(int[] arr){ arr=buildMaxHeap(arr);//堆創建,第一個元素是最大的 for(int i=arr.length-1;i>0;i--){ int temp=arr[0];//將堆頂元素和堆底元素進行交換 arr[0]=arr[i]; arr[i]=temp; adjustDownToTop(arr,0,i); } System.out.println(Arrays.toString(arr)); }