知識星球（點選上方公眾號，可快速關註）
來源：程式員小灰
在上一篇漫畫中，小灰介紹了 二叉堆 這樣一種強大的資料結構：
那麼，這個二叉堆怎樣來使用呢？我們這一期將會詳細講述。
讓我們回顧一下二叉堆和最大堆的特性：
1.二叉堆本質上是一種完全二叉樹
2.最大堆的堆頂是整個堆中的最大元素
當我們刪除一個最大堆的堆頂（並不是完全刪除，而是替換到最後面），經過自我調節，第二大的元素就會被交換上來，成為最大堆的新堆頂。
正如上圖所示，當我們刪除值為10的堆頂節點，經過調節，值為9的新節點就會頂替上來；當我們刪除值為9的堆頂節點，經過調節，值為8的新節點就會頂替上來…….
由於二叉堆的這個特性，我們每一次刪除舊堆頂，調整後的新堆頂都是大小僅次於舊堆頂的節點。那麼我們只要反覆刪除堆頂，反覆調節二叉堆，所得到的集合就成為了一個有序集合，過程如下：
刪除節點9，節點8成為新堆頂：
刪除節點8，節點7成為新堆頂：
刪除節點7，節點6成為新堆頂：
刪除節點6，節點5成為新堆頂：
刪除節點5，節點4成為新堆頂：
刪除節點4，節點3成為新堆頂：
刪除節點3，節點2成為新堆頂：
到此為止，我們原本的最大堆已經變成了一個從小到大的有序集合。之前說過二叉堆實際儲存在陣列當中，陣列中的元素排列如下：
由此，我們可以歸納出堆排序演演算法的步驟：
1. 把無序陣列構建成二叉堆。
2. 迴圈刪除堆頂元素，移到集合尾部，調節堆產生新的堆頂。
public class HeapSort {
/**
* 下沉調整
* @param array 待調整的堆
* @param parentIndex 要下沉的父節點
* @param parentIndex 堆的有效大小
*/
public static void downAdjust(int[] array, int parentIndex, int length) {
// temp儲存父節點值，用於最後的賦值
int temp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
// 如果有右孩子，且右孩子大於左孩子的值，則定位到右孩子
if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
childIndex++;
}
// 如果父節點小於任何一個孩子的值，直接跳出
if (temp >= array[childIndex])
break;
//無需真正交換，單向賦值即可
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = temp;
}
/**
* 堆排序
* @param array 待調整的堆
*/
public static void heapSort(int[] array) {
// 1.把無序陣列構建成二叉堆。
for (int i = (array.length-2)/
2; i >= 0; i--) {
downAdjust(array, i, array.length);
}
System.out.println(Arrays.toString(array));
// 2.迴圈刪除堆頂元素，移到集合尾部，調節堆產生新的堆頂。
for (int i = array.length - 1; i > 0; i--) {
// 最後一個元素和第一元素進行交換
int temp = array[i];
array[i] = array[0];
array[0] = temp;
// 下沉調整最大堆
downAdjust(array, 0, i);
}
}
public static void main(String[] args) {
int[] arr = new int[] {1,3,2,6,5,7,8,9,10,0};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}
二叉堆的節點下沉調整（downAdjust 方法）是堆排序演演算法的基礎，這個調節操作本身的時間複雜度是多少呢？
假設二叉堆總共有n個元素，那麼下沉調整的最壞時間複雜度就等同於二叉堆的高度，也就是O（logn）。
我們再來回顧一下堆排序演演算法的步驟：
1. 把無序陣列構建成二叉堆。
2. 迴圈刪除堆頂元素，移到集合尾部，調節堆產生新的堆頂。
第一步，把無序陣列構建成二叉堆，需要進行n/2次迴圈。每次迴圈呼叫一次 downAdjust 方法，所以第一步的計算規模是 n/2 * logn，時間複雜度O（nlogn）。
第二步，需要進行n-1次迴圈。每次迴圈呼叫一次 downAdjust 方法，所以第二步的計算規模是 （n-1） * logn ，時間複雜度 O（nlogn）。
兩個步驟是併列關係，所以整體的時間複雜度同樣是 O（nlogn）。
【關於投稿】
如果大家有原創好文投稿，請直接給公號傳送留言。
① 留言格式：
【投稿】+《 文章標題》+ 文章連結
② 示例：
【投稿】《不要自稱是程式員，我十多年的 IT 職場總結》：
http://blog.jobbole.com/94148/
③ 最後請附上您的個人簡介哈~
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
