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

首先介紹幾個(gè)概念：

衛(wèi)星數(shù)據(jù)：一個(gè)帶排序的的數(shù)通常是有一個(gè)稱為記錄的數(shù)據(jù)集組成的，每一個(gè)記錄有一個(gè)關(guān)鍵字key，記錄的其他數(shù)據(jù)稱為衛(wèi)星數(shù)據(jù)。

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

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

我以前總結(jié)過堆排序，并具體實(shí)現(xiàn)了堆排序，代碼中給出了詳細(xì)的注釋，所以在這里就不重復(fù)發(fā)了，大家可以去看看，個(gè)人覺得總結(jié)的還是比較給力的：

這里再補(bǔ)充幾點(diǎn)：

1.區(qū)別length[A]和heap-sort[A]。(P73)(這個(gè)在下一篇的優(yōu)先級隊(duì)列中將會具體區(qū)別)

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

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

所以這也是我喜歡《算法導(dǎo)論》的原因，接下來，就要強(qiáng)烈推薦大家看《算法導(dǎo)論》上非常非常給力的堆排序?qū)崿F(xiàn)圖了—圖6-4。

總結(jié)：本章最基礎(chǔ)也是最重要的就是理解堆這種結(jié)構(gòu)！

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

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

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

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

對，堆排序就是利用的這個(gè)特性—“堆的最大元素就存放在根結(jié)點(diǎn)中”

每次堆化，這樣就找到了當(dāng)前堆的最大元素。

所以說，理解了其本質(zhì)特征，堆排序其實(shí)很簡單的。

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

下一篇將實(shí)現(xiàn)最大優(yōu)先級隊(duì)列。