建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

首先介紹幾個概念：

衛星數據：一個帶排序的的數通常是有一個稱為記錄的數據集組成的，每一個記錄有一個關鍵字key，記錄的其他數據稱為衛星數據。

原地排序：在排序輸入數組時，只有常數個元素被存放到數組以外的空間中去。

在第二章介紹了兩種排序：插入排序和合并排序，接下來兩章要介紹的是推排序和快速排序，這四個排序都屬于比較排序(comparison sort)。

我以前總結過堆排序，并具體實現了堆排序，代碼中給出了詳細的注釋，所以在這里就不重復發了，大家可以去看看，個人覺得總結的還是比較給力的：

這里再補充幾點：

1.區別length[A]和heap-sort[A]。(P73)(這個在下一篇的優先級隊列中將會具體區別)

2.總體上看堆排序由三個函數組成：①.MAX-HEAPIFY ②.BUILD-MAX-HEAP ③.HEAP-SORT

另外，在這里給大家補充一點個人經驗，有時理論難以理解，代碼難以理解，這個時候，就要靠秘訣了：拿起手中的筆和紙，自己給出一組輸入，按照書上的代碼，自己去模擬這組輸入的執行過程。(這個過程人人都知道，但并不是人人都去做了！學算法，就要自己去模擬，去畫圖，去推！怎么樣容易理解就怎么去做！)

所以這也是我喜歡《算法導論》的原因，接下來，就要強烈推薦大家看《算法導論》上非常非常給力的堆排序實現圖了—圖6-4。

總結：本章最基礎也是最重要的就是理解堆這種結構！

堆是什么？來看看《算法導論》上的圖6-1：

圖(a)是一個最大堆，圖(b)是最大堆的數組表示。可以看到堆的數組并不是已排序好的。

讓我們來回憶下最大堆的定義(P74)：

在最大堆中，最大堆特性是指除了根以外的每個結點i，有A[PARENT(i)] >= A[i]。這樣，堆的最大元素就存放在根結點中。

對，堆排序就是利用的這個特性—“堆的最大元素就存放在根結點中”

每次堆化，這樣就找到了當前堆的最大元素。

所以說，理解了其本質特征，堆排序其實很簡單的。

至于堆排序的具體應用，在后面的最短路算法—Dijkstra中，會用到由堆來優化普通的Dijkstra算法。

下一篇將實現最大優先級隊列。