版權(quán)聲明：本文源自簡(jiǎn)書tianma流椒，轉(zhuǎn)載請(qǐng)務(wù)必注明出處：http://www.reibang.com/p/ad3082312012
概念
堆： 堆是具有下列性質(zhì)的完全二叉樹：每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子（如果存在的話）的值叁扫，稱為最大堆；或者每個(gè)節(jié)點(diǎn)的值都小于或等于其左右孩子（如果存在的話）的值供鸠，稱為最小堆。
完全二叉樹：
最大堆：
最小堆：
圖片來源: 常見排序算法 - 堆排序 (Heap Sort)
堆排序：利用堆（這里使用最大堆）進(jìn)行排序的方法。其基本思想是：將待排序的序列構(gòu)造成一個(gè)最大堆摔癣，此時(shí)待排序序列的最大值就是堆頂?shù)母?jié)點(diǎn)，將其移走（其實(shí)就是將其與待排序序列的最后一個(gè)元素進(jìn)行交換，此時(shí)待排序序列最后一個(gè)元素就是最大值）择浊，然后將剩余的序列重新構(gòu)造成一個(gè)堆戴卜，如此反復(fù)，直到待排序序列只有一個(gè)元素為止琢岩，則排序完成投剥。
性質(zhì)
已知arr[0...n-1]是長(zhǎng)度為n的最大堆數(shù)組，下標(biāo)從0開始粘捎，那么對(duì)于下標(biāo)為i的節(jié)點(diǎn)I薇缅，有：
(1). 如果I的左孩子存在的話，那么I的左孩子節(jié)點(diǎn)的下標(biāo)為 left(i) = 2*i+1攒磨；
(2). 如果I的右孩子存在的話泳桦，那么I的右孩子節(jié)點(diǎn)的下標(biāo)為 right(i) = 2*i+2;
(3). 如果I雙親節(jié)點(diǎn)存在的話，那么I的雙親節(jié)點(diǎn)的下標(biāo)為 parent(i) = (i-1)/2; (向下取整)
基本操作
- 構(gòu)建最大堆 buildMaxHeap(int[] arr)：將待排序序列arr構(gòu)建成最大堆娩缰；
- 調(diào)整最大堆 adjustHeap(int arr[], int begin, int end): 已知arr[begin]的左子樹和右子樹都滿足最大堆灸撰，那么調(diào)節(jié)節(jié)點(diǎn)arr[begin]，將以arr[begin]為根節(jié)點(diǎn)的二叉樹調(diào)整為最大堆拼坎。
對(duì)于堆排序浮毯，最重要的就是構(gòu)建最大堆和調(diào)整最大堆，其實(shí)構(gòu)造初始堆事實(shí)上也是調(diào)整堆的過程泰鸡，只不過構(gòu)造初始堆是對(duì)所有的非葉節(jié)點(diǎn)都進(jìn)行調(diào)整债蓝。
Java實(shí)現(xiàn)
// 定義接口
interface Sorter {
/**
* 將數(shù)組按升序排序
*/
int[] sort(int[] arr);
/**
* 交換數(shù)組arr中的第i個(gè)位置和第j個(gè)位置的關(guān)鍵字
*/
default void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 堆排序
class HeapSorter implements Sorter {
@Override
public int[] sort(int[] arr) {
heapSort(arr);
return arr;
}
private void heapSort(int[] arr) {
buildMaxHeap(arr); // 構(gòu)建最大堆
// 將最大堆堆頂元素與數(shù)組末尾元素交換，并將前n-1序列重新構(gòu)造成最大堆,重復(fù)n-1次
for (int i = arr.length - 1; i >= 1; i--) {
swap(arr, 0, i); // 將堆頂元素和當(dāng)前未經(jīng)排序的子序列的最后一個(gè)元素進(jìn)行交換
adjustHeap(arr, 0, i - 1); // 將arr[0...i-1](前i個(gè)元素)重新調(diào)整為最大堆
}
}
/**
* 將指定數(shù)組arr構(gòu)建成最大堆
*/
private void buildMaxHeap(int[] arr) {
int len = arr.length;
// 從最后一個(gè)非葉子節(jié)點(diǎn)往前遍歷盛龄，將當(dāng)前序列構(gòu)成最大堆
for (int i = len / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, len - 1);
}
}
/**
* 假定arr[begin]的左子樹和右子樹均滿足最大堆饰迹，那么調(diào)節(jié)節(jié)點(diǎn)arr[begin]，將以arr[begin]為根節(jié)點(diǎn)的二叉樹調(diào)整為最大堆余舶。
*/
private void adjustHeap(int[] arr, int begin, int end) {
int tmp = arr[begin];
int j;
for (j = 2 * begin + 1; j <= end; j = 2 * j + 1) {
// j=2*begin+1表示j對(duì)應(yīng)二叉樹節(jié)點(diǎn)的左孩子
if (j + 1 <= end && arr[j] < arr[j + 1]) {
// 如果當(dāng)前節(jié)點(diǎn)的右孩子存在且左孩子的值小于右孩子
j++; // j為左右孩子較大記錄的下標(biāo)
}
if (tmp >= arr[j]) // tmp的值已經(jīng)大于arr[j]啊鸭，則調(diào)整完畢，跳出循環(huán)
break;
arr[begin] = arr[j]; // 當(dāng)前根節(jié)點(diǎn)并未均大于左右節(jié)點(diǎn)(如果有的話)匿值，重新給當(dāng)前根節(jié)點(diǎn)賦值
begin = j; // begin指向新的可能需要進(jìn)行最大堆調(diào)整的子樹的根節(jié)點(diǎn)
}
arr[begin] = tmp;
}
}
堆排序其實(shí)也是一種選擇排序赠制，是一種樹形選擇排序。在簡(jiǎn)單選擇排序中挟憔，從arr[0...n-1]中選擇最兄有（或最大）記錄，需要比較n-1次绊谭，然后再從剩下arr[1...n-1]的n-1個(gè)元素中選擇最欣逋佟（或最大）記錄，需要比較n-2次龙誊。然而事實(shí)上這n-2次比較中抚垃，有許多已經(jīng)在前一趟n-1次的比較中做過了；而樹形選擇排序恰好利用樹形的特點(diǎn)保存了部分前面的比較結(jié)果，因此可以減少比較次數(shù)鹤树，提高算法效率铣焊。
復(fù)雜度
時(shí)間復(fù)雜度：
對(duì)于n個(gè)關(guān)鍵字序列，每個(gè)節(jié)點(diǎn)需比較log2(n)次罕伯，因此其時(shí)間復(fù)雜度為O(nlogn)曲伊。
由于堆排序?qū)υ加涗浀呐判驙顟B(tài)并不敏感，所以它的最好追他、最壞坟募、平均時(shí)間復(fù)雜度均為O(nlogn)
由于初始構(gòu)建堆所需要的比較次數(shù)較多，所以堆排序不適合待排序序列個(gè)數(shù)少的情況邑狸。
空間復(fù)雜度：
最好情況=平均情況=最壞情況=O(1)
