[TOC]
## 算法原理
先上一張堆排序動畫演示圖片：
[](https://box.kancloud.cn/2015-07-26_55b456f07354c.gif "圖片來自維基百科")
圖片來自維基百科
**1\. 不得不說說二叉樹**
要了解堆首先得了解一下[二叉樹](http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91)，在計算機科學中，二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現[二叉查找樹](http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9)和[二叉堆](http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E5%A0%86)。
二叉樹的每個結點至多只有二棵子樹（不存在度大于 2 的結點），二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第 i 層至多有 2i?- 1 個結點；深度為 k 的二叉樹至多有 2k?- 1 個結點；對任何一棵二叉樹 T，如果其終端結點數為 n0，度為 2 的結點數為 n2，則n0?= n2?+ 1。
樹和二叉樹的三個主要差別：
* 樹的結點個數至少為 1，而二叉樹的結點個數可以為 0
* 樹中結點的最大度數沒有限制，而二叉樹結點的最大度數為 2
* 樹的結點無左、右之分，而二叉樹的結點有左、右之分
二叉樹又分為完全二叉樹（complete binary tree）和滿二叉樹（full binary tree）
滿二叉樹：一棵深度為 k，且有 2k?- 1 個節點稱之為滿二叉樹
[](https://box.kancloud.cn/2015-07-26_55b456fd1c9e6.png "深度為 3 的滿二叉樹 full binary tree")
深度為 3 的滿二叉樹 full binary tree
完全二叉樹：深度為 k，有 n 個節點的二叉樹，當且僅當其每一個節點都與深度為 k 的滿二叉樹中序號為 1 至 n 的節點對應時，稱之為完全二叉樹
[](https://box.kancloud.cn/2015-07-26_55b457076f6f5.png "深度為 3 的完全二叉樹 complete binary tree")
深度為 3 的完全二叉樹 complete binary tree
**2\. 什么是堆？**
堆（二叉堆）可以視為一棵完全的二叉樹，完全二叉樹的一個“優秀”的性質是，除了最底層之外，每一層都是滿的，這使得堆可以利用數組來表示（普通的一般的二叉樹通常用鏈表作為基本容器表示），每一個結點對應數組中的一個元素。
如下圖，是一個堆和數組的相互關系
[](https://box.kancloud.cn/2015-07-26_55b4571042a0a.png "堆和數組的相互關系")
堆和數組的相互關系
對于給定的某個結點的下標 i，可以很容易的計算出這個結點的父結點、孩子結點的下標：
* Parent(i) = floor(i/2)，i 的父節點下標
* Left(i) = 2i，i 的左子節點下標
* Right(i) = 2i + 1，i 的右子節點下標
[](https://box.kancloud.cn/2015-07-26_55b45710897d7.png)
二叉堆一般分為兩種：最大堆和最小堆。
最大堆：
* 最大堆中的最大元素值出現在根結點（堆頂）
* 堆中每個父節點的元素值都大于等于其孩子結點（如果存在）
[](https://box.kancloud.cn/2015-07-26_55b45710bd585.png "最大堆")
最大堆
最小堆：
* 最小堆中的最小元素值出現在根結點（堆頂）
* 堆中每個父節點的元素值都小于等于其孩子結點（如果存在）
[](https://box.kancloud.cn/2015-07-26_55b4571112559.png "最小堆")
最小堆
**3\. 堆排序原理**
> 堆排序就是把最大堆堆頂的最大數取出，將剩余的堆繼續調整為最大堆，再次將堆頂的最大數取出，這個過程持續到剩余數只有一個時結束。在堆中定義以下幾種操作：
> * 最大堆調整（Max-Heapify）：將堆的末端子節點作調整，使得子節點永遠小于父節點
> * 創建最大堆（Build-Max-Heap）：將堆所有數據重新排序，使其成為最大堆
> * 堆排序（Heap-Sort）：移除位在第一個數據的根節點，并做最大堆調整的遞歸運算
繼續進行下面的討論前，需要注意的一個問題是：數組都是 Zero-Based，這就意味著我們的堆數據結構模型要發生改變
[](https://box.kancloud.cn/2015-07-26_55b4571146cea.png "Zero-Based")Zero-Based
相應的，幾個計算公式也要作出相應調整：
* Parent(i) = floor((i-1)/2)，i 的父節點下標
* Left(i) = 2i + 1，i 的左子節點下標
* Right(i) = 2(i + 1)，i 的右子節點下標
最大堆調整（MAX‐HEAPIFY）的作用是保持最大堆的性質，是創建最大堆的核心子程序，作用過程如圖所示：
[](https://box.kancloud.cn/2015-07-26_55b4571192f0c.png "Max-Heapify")
Max-Heapify
由于一次調整后，堆仍然違反堆性質，所以需要遞歸的測試，使得整個堆都滿足堆性質，用 JavaScript 可以表示如下：
~~~
/**
* 從 index 開始檢查并保持最大堆性質
*
* @array
*
* @index 檢查的起始下標
*
* @heapSize 堆大小
*
**/
function maxHeapify(array, index, heapSize) {
var iMax = index,
iLeft = 2 * index + 1,
iRight = 2 * (index + 1);
if (iLeft
iMax = iLeft;
}
if (iRight
iMax = iRight;
}
if (iMax != index) {
swap(array, iMax, index);
maxHeapify(array, iMax, heapSize); // 遞歸調整
}
}
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
~~~
通常來說，遞歸主要用在分治法中，而這里并不需要分治。而且遞歸調用需要壓棧/清棧，和迭代相比，性能上有略微的劣勢。當然，按照20/80法則，這是可以忽略的。但是如果你覺得用遞歸會讓自己心里過不去的話，也可以用迭代，比如下面這樣：
~~~
/**
* 從 index 開始檢查并保持最大堆性質
*
* @array
*
* @index 檢查的起始下標
*
* @heapSize 堆大小
*
**/
function maxHeapify(array, index, heapSize) {
var iMax, iLeft, iRight;
while (true) {
iMax = index;
iLeft = 2 * index + 1;
iRight = 2 * (index + 1);
if (iLeft
iMax = iLeft;
}
if (iRight
iMax = iRight;
}
if (iMax != index) {
swap(array, iMax, index);
index = iMax;
} else {
break;
}
}
}
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
~~~
創建最大堆（Build-Max-Heap）的作用是將一個數組改造成一個最大堆，接受數組和堆大小兩個參數，Build-Max-Heap 將自下而上的調用 Max-Heapify 來改造數組，建立最大堆。因為 Max-Heapify 能夠保證下標 i 的結點之后結點都滿足最大堆的性質，所以自下而上的調用 Max-Heapify 能夠在改造過程中保持這一性質。如果最大堆的數量元素是 n，那么 Build-Max-Heap 從 Parent(n) 開始，往上依次調用 Max-Heapify。流程如下：
[](https://box.kancloud.cn/2015-07-26_55b457121b1f3.png "Build-Max-Heap")
Build-Max-Heap
用 JavaScript 描述如下：
~~~
function buildMaxHeap(array, heapSize) {
var i,
iParent = Math.floor((heapSize - 1) / 2);
for (i = iParent; i >= 0; i--) {
maxHeapify(array, i, heapSize);
}
}
~~~
堆排序（Heap-Sort）是堆排序的接口算法，Heap-Sort先調用Build-Max-Heap將數組改造為最大堆，然后將堆頂和堆底元素交換，之后將底部上升，最后重新調用Max-Heapify保持最大堆性質。由于堆頂元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分離出堆，重復n-1次之后，數組排列完畢。整個流程如下：
[](https://box.kancloud.cn/2015-07-26_55b457127e46f.png "Heap-Sort")
Heap-Sort
用 JavaScript 描述如下：
~~~
function heapSort(array, heapSize) {
buildMaxHeap(array, heapSize);
for (int i = heapSize - 1; i > 0; i--) {
swap(array, 0, i);
maxHeapify(array, 0, i);
}
}
~~~
## JavaScript 語言實現
最后，把上面的整理為完整的 javascript 代碼如下：
~~~
function heapSort(array) {
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
function maxHeapify(array, index, heapSize) {
var iMax,
iLeft,
iRight;
while (true) {
iMax = index;
iLeft = 2 * index + 1;
iRight = 2 * (index + 1);
if (iLeft < heapSize && array[index] < array[iLeft]) {
iMax = iLeft;
}
if (iRight < heapSize && array[iMax] < array[iRight]) {
iMax = iRight;
}
if (iMax != index) {
swap(array, iMax, index);
index = iMax;
} else {
break;
}
}
}
function buildMaxHeap(array) {
var i,
iParent = Math.floor(array.length / 2) - 1;
for (i = iParent; i >= 0; i--) {
maxHeapify(array, i, array.length);
}
}
function sort(array) {
buildMaxHeap(array);
for (var i = array.length - 1; i > 0; i--) {
swap(array, 0, i);
maxHeapify(array, 0, i);
}
return array;
}
return sort(array);
}
~~~
## 參考文章
* [Wikipedia](http://en.wikipedia.org/wiki/Heapsort)
* [維基百科，堆排序](http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F)
* [維基百科，二叉樹](http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91)
* [Algorithms Chapter 6 Heapsort](http://ind.ntou.edu.tw/~litsnow/al98/pdf/Algorithm-Ch6-Heapsort.pdf)
* [Heap Sort](http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm)
* [堆與堆排序](http://blog.kingsamchen.com/archives/547#viewSource)
* [堆排序](http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.4.2.1.htm)
* [堆排序(Heap Sort)算法學習](http://www.nowamagic.net/algorithm/algorithm_HeapSortStudy.php)
* [Sorting Algorithm Animations](http://www.sorting-algorithms.com/)
