基本思想
堆的定義n個(gè)關(guān)鍵字序列kl，k2，…，kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)之一（簡(jiǎn)稱堆性質(zhì)）：
ki≤k2i且ki≤k2i+1 或ki≥k2i且ki≥k2i+1（1≤i≤FLOOR(n/2)）若將此序列所存儲(chǔ)的向量R[1..n]看做是一棵完全二叉樹的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左右孩子（若 存在）結(jié)點(diǎn)的關(guān)鍵字。
小根堆：根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小的。大根堆：根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大的。我們可以選擇大根堆或者小根堆中的任意一個(gè)來進(jìn)行排序。
排序思想用大根堆排序的基本思想：
先將初始文件R[1..n]建成一個(gè)大根堆，此堆為初始的無序區(qū)。再將關(guān)鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個(gè)記錄R[n]交換，由此得 到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key。由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。 然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，由 此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系 R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。算法實(shí)現(xiàn)
堆排序算法，java實(shí)現(xiàn)，代碼如下所示：
public abstract class Sorter { public abstract void sort(int[] array); } public class HeapSorter extends Sorter { public void sort(int[] array) { heapSort(array); } /** * <p>堆排序方法 * <p>基于大根堆的堆排序方法 */ PRivate void heapSort(int[] array) { Integer tmp; // 用于交換的暫存單元 buildHeap(array); // 執(zhí)行初始建堆，并調(diào)整 for (int i = 0; i < array.length; i++) { // 交換堆頂元素array[0]和堆中最后一個(gè)元素array[array.length-1-i] tmp = array[0]; array[0] = array[array.length - 1 - i]; array[array.length - 1 - i] = tmp; // 每次交換堆頂元素和堆中最后一個(gè)元素之后，都要對(duì)堆進(jìn)行調(diào)整 adjustHeap(array, 0, array.length - 1 - i); } } /** * 建堆方法 * 調(diào)整堆中0~array.length/2個(gè)結(jié)點(diǎn)，保持堆的性質(zhì) * */ private void buildHeap(int[] array) { // 求出當(dāng)前堆中最后一個(gè)存在孩子結(jié)點(diǎn)的索引 int pos = (array.length - 1) / 2; // 從該結(jié)點(diǎn)結(jié)點(diǎn)開始，執(zhí)行建堆操作 for (int i = pos; i >= 0; i--) { adjustHeap(array, i, array.length); // 在建堆過程中，及時(shí)調(diào)整堆中索引為i的結(jié)點(diǎn) } } /** * <p> * 調(diào)整堆的方法 * * @param s 待調(diào)整結(jié)點(diǎn)的索引 * @param m 待調(diào)整堆的結(jié)點(diǎn)的數(shù)量(亦即：排除葉子結(jié)點(diǎn)) */ private void adjustHeap(int[] array, int s, int m) { Integer tmp = array[s]; // 當(dāng)前待調(diào)整的結(jié)點(diǎn) int i = 2 * s + 1; // 當(dāng)前待調(diào)整結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的索引(i+1為當(dāng)前調(diào)整結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的索引) while (i < m) { if (i + 1 < m && array[i] < array[i + 1]) { // 如果右孩子大于左孩子(找到比當(dāng)前待調(diào)整結(jié)點(diǎn)大的孩子結(jié)點(diǎn)) i = i + 1; } if (array[s] < array[i]) { array[s] = array[i]; // 孩子結(jié)點(diǎn)大于當(dāng)前待調(diào)整結(jié)點(diǎn)，將孩子結(jié)點(diǎn)放到當(dāng)前待調(diào)整結(jié)點(diǎn)的位置上 s = i; // 重新設(shè)置待調(diào)整的下一個(gè)結(jié)點(diǎn)的索引 i = 2 * s + 1; } else { // 如果當(dāng)前待調(diào)整結(jié)點(diǎn)大于它的左右孩子，則不需要調(diào)整，直接退出 break; } array[s] = tmp; // 當(dāng)前待調(diào)整的結(jié)點(diǎn)放到比其大的孩子結(jié)點(diǎn)位置上 } } }排序過程
假設(shè)待排序數(shù)組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數(shù)組大小為20。
第一步：初始建堆首先執(zhí)行的初始建堆（在建堆的過程中需要調(diào)整堆）。過程如下：
求出當(dāng)前堆中最后一個(gè)存在孩子結(jié)點(diǎn)的索引這里，把數(shù)組array看做是一棵完全二叉樹，這樣數(shù)組每個(gè)索引位置上的元素都對(duì)應(yīng)到二叉樹中的結(jié)點(diǎn)，如圖所示：
其中需要在這棵樹中找到最后一個(gè)有孩子最大的一個(gè)結(jié)點(diǎn)的索引：pos = (array.length-1)/2 = (20-1)/2 = 9也就是索引為9的array[9] = 76，由后至前層次遍歷，從array[9]一直到array[0]，對(duì)初始堆進(jìn)行調(diào)整。
先比較array[9] = 76的左右孩子：s = 9，i = 2*s+1 = 2*9 + 1 = 19，而i+1 = 19 + 1 = 20 > m = array.length-1 = 20 -1 = 19(array[9] = 76沒有右孩子)，只需要將array[9] = 76與array[i] = array[19] = 49比較，因?yàn)閍rray[9] = 76>array[i] = array[19] = 49，則不需要交換array[9] = 76與array[i] = array[19] = 49，繼續(xù)對(duì)下一個(gè)結(jié)點(diǎn)（也就是array[8] = 55）進(jìn)行調(diào)整；
調(diào)整結(jié)點(diǎn)array[8] = 55：先比較array[8] = 55的左右孩子：s = 8，i = 2*s+1 = 2*8 + 1 = 17,，而i+1 = 17 + 1 = 18 < m = array.length-1 = 20-1 = 19(array[8] = 55存在右孩子)，左孩子array[i] = array[17] = 65小于右孩子array[i+1] = array[18] = 76，只需要將array[8] = 76與右孩子array[i+1] = array[18] = 76比較，因?yàn)閍rray[8] = 55<array[i+1] = array[18] = 76，則需要交換array[8] = 55與array[i+1] = array[18] = 76，交換后如圖所示：
繼續(xù)對(duì)下一個(gè)結(jié)點(diǎn)（也就是array[8] = 55）進(jìn)行調(diào)整；
顯然，不需要交換；
調(diào)整結(jié)點(diǎn)array[6] = 0：調(diào)整結(jié)果如圖所示：
調(diào)整結(jié)果如圖所示：
調(diào)整結(jié)果如圖所示：
顯然，不需要交換。
調(diào)整結(jié)點(diǎn)array[2] = 34：調(diào)整結(jié)果如圖所示：
調(diào)整結(jié)果如圖所示：
顯然，不需要交換。
至此，對(duì)初始堆的調(diào)整完成。
第二步：第一次交換將堆頂元素與最后一個(gè)元素交換，即array[0] = 94與最后一個(gè)元素array[19] = 49交換，如圖所示：
此時(shí)，數(shù)組為：array = {49,76,90,12,76,68,34,37,76,26,37,5,9,83,0,37,12,65,55,94}數(shù)組中最大的元素被交換到了數(shù)組的末尾，也就是array[19] = 94是最終排好序的固定位置。
第三步：調(diào)整堆過程同前面類似?！詈蠼?jīng)過堆排序得到有序的數(shù)組。
算法分析
時(shí)間復(fù)雜度堆排序的時(shí)間，主要由建立初始堆和反復(fù)重建堆這兩部分的時(shí)間開銷構(gòu)成。堆排序的最壞時(shí)間復(fù)雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。
空間復(fù)雜度堆排序過程中，需要調(diào)整堆，交換待排序記錄需要一個(gè)臨時(shí)存儲(chǔ)單元，所以空間復(fù)雜度為O(1)。
排序穩(wěn)定性堆排序是就地排序，它是不穩(wěn)定的排序方法。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
