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

首先介紹幾個概念：

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

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

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

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

這里再補充幾點：

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

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

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

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

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

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

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

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

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

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

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

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

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

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