一、堆(Heap)定義

（1）n個關鍵字序列Kl，K2，…，Kn稱為（Heap），當且僅當該序列滿足如下性質（簡稱為堆性質）：

? ? ? ?k(i)<=k(2i）且k(i)<=k(2i+1)(1≤i≤ n/2），

? ? ? ?當然，這是小根堆，大根堆則換成>=號。

（2）k(i）相當于二叉樹的非葉子結點，K(2i）則是左子節點，k(2i+1）是右子節點

? ? ? ?若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：
樹中任一非葉子結點的關鍵字均不大于（或不小于）其左右孩子（若存在）結點的關鍵字。

?

二、堆排序的思想

堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特征，使得在當前無序區中選取最大（或最小）關鍵字的記錄變得簡單。 （1）用大根堆排序的基本思想 ① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區 ② 再將關鍵字最大的記錄R[1]（即堆頂）和無序區的最后一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key ③由于交換后新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最后一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。 …… 直到無序區只有一個元素為止。

?

三、算法實現

/*** 堆排序* @param data 數據隊列*/public static void heapSort(int[] data) {//初始化大堆for (int i = data.length / 2 - 1; i >= 0; i--) {adjustHeap(data, i, data.length); //指定父節點堆調整 }int temp; //臨時空間for (int i = data.length - 1; i > 0; i--) {//堆首與堆尾交換temp = data[i];data[i] = data[0];data[0] = temp;//大堆調整adjustHeap(data, 0, i);}}/*** 堆調整* @param data 數據隊列* @param start 起始位置* @param end 截止位置，是堆尾的下一個位置*/public static void adjustHeap(int[] data, int start, int end) {int src=data[start]; //保存起始位置的值for (int i = start * 2 + 1; i < end; i = i * 2 + 1) {//判斷左右節點大小if (i + 1 < end && data[i] < data[i + 1]) {i++; //右節點大 }//起始位置值最大if(src >= data[i])break;data[start]=data[i];//賦值最大值start=i; //記錄大值的位置 }data[start]=src;//回填起始值}

?

四、算法復雜度

堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用adjustHeap實現的。

? ? ?平均性能O(N*logN)，由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。

堆排序是就地排序，輔助空間為O(1）. 它是不穩定的排序方法。（排序的穩定性是指如果在排序的序列中，存在前后相同的兩個元素的話，排序前 和排序后他們的相對位置不發生變化）

?

總結

以上是生活随笔為你收集整理的算法三之堆排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。