堆排序可以做什么
首先應(yīng)該弄清楚堆排序可以解決什么問(wèn)題承疲，答案是顯而易見(jiàn)的：排序阳距。說(shuō)得通俗點(diǎn)兒就是對(duì)一組無(wú)序的數(shù)字進(jìn)行調(diào)整，使其按照從大到小或者從小大到的順序有序排列。我們習(xí)慣性的采用數(shù)組這一數(shù)據(jù)結(jié)構(gòu)來(lái)記錄一系列有序或者無(wú)序的數(shù)據(jù)尺借。
故我們可以借助堆排序這種方法份汗，將以下無(wú)序數(shù)組:
| 4 | 5 | 3 | 2 | 6 | 1 |
|---|
調(diào)整為有序數(shù)組：
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|
以下講解的所有內(nèi)容都是為了將上述無(wú)序數(shù)組經(jīng)過(guò)堆排序后調(diào)整為從大到小的有序數(shù)組盈电。
什么是堆
上一小節(jié)重在堆排序中的“排序”二字，這一節(jié)我們來(lái)嘮嘮“堆”杯活。我在沒(méi)有接觸“堆”這個(gè)概念之前匆帚，確實(shí)感覺(jué)丈二和尚摸不著頭腦，甚至還會(huì)與“堆內(nèi)存”的“堆”概念聯(lián)系起來(lái)旁钧。下面就讓我們先來(lái)看看堆的定義吧吸重。
根據(jù)《Data Structures and Algorithm Analysis in C》(中文譯名：《數(shù)據(jù)結(jié)構(gòu)與算法分析》）和百度百科的相關(guān)資料，堆必須同時(shí)具備兩個(gè)特性：1歪今、結(jié)構(gòu)性嚎幸；2）堆序性。
1寄猩、結(jié)構(gòu)性
堆是一棵完全二叉樹(shù)鞭铆，所謂完全二叉樹(shù)即葉節(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置的二叉樹(shù)焦影。
以如下無(wú)序數(shù)組A為例
| 4 | 5 | 3 | 2 | 6 | 1 |
|---|
可將其表示為完全二叉樹(shù)的形式(從左至右车遂，從上到下依次填入二叉樹(shù))：
提到二叉樹(shù)就不得不提父節(jié)點(diǎn)與左、右子節(jié)點(diǎn)的概念斯辰。在二叉樹(shù)中舶担，一個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)的取值范圍為[0,2],子節(jié)點(diǎn)數(shù)為零的父節(jié)點(diǎn)常被稱(chēng)為葉子節(jié)點(diǎn)。每一個(gè)父節(jié)點(diǎn)又可以看成是其子樹(shù)分支的根節(jié)點(diǎn)彬呻。
綜合數(shù)組和二叉樹(shù)解結(jié)構(gòu)來(lái)看衣陶，在知道了某一數(shù)字在數(shù)組中的索引后，可以很方便地計(jì)算出二叉樹(shù)中該數(shù)字的左右子節(jié)點(diǎn)闸氮，或者父節(jié)點(diǎn)在數(shù)組中的索引剪况。
以數(shù)字5為例，它的數(shù)組表示為A[1],根據(jù)二叉樹(shù)蒲跨，其父節(jié)點(diǎn)為4译断，即A[0];同時(shí)其左節(jié)點(diǎn)為2，右節(jié)點(diǎn)為6或悲，分別對(duì)應(yīng)A[3],A[4]孙咪。
故可得出一個(gè)結(jié)論堪唐，A[i]的左節(jié)點(diǎn)為A[2i+1],右節(jié)點(diǎn)為A[2i+2]，父節(jié)點(diǎn)為A[i/2]翎蹈，它從數(shù)組索引的角度描述了數(shù)字與數(shù)字在二叉樹(shù)中的位置關(guān)系淮菠。（1、在應(yīng)用此結(jié)論時(shí)需確認(rèn)A[i]存在相應(yīng)的左節(jié)點(diǎn)荤堪、右節(jié)點(diǎn)合陵、根節(jié)點(diǎn)；2澄阳、此結(jié)論在后面會(huì)反復(fù)用到曙寡；3、此結(jié)論實(shí)際上是完全二叉樹(shù)的一個(gè)基本性質(zhì)寇荧，這也是為什么堆的結(jié)構(gòu)性要求其滿(mǎn)足完全二叉樹(shù)的形式，就是為了使用此結(jié)論）
2执隧、堆序性
堆序性說(shuō)得通俗一點(diǎn)兒就是揩抡，父節(jié)點(diǎn)中的元素不小于（不大于）任意子節(jié)點(diǎn)的元素。這里的元素在本文中是以數(shù)字體現(xiàn)的镀琉。注：本文只討論“大根堆”峦嗤，即父節(jié)點(diǎn)中的元素不小于任意子節(jié)點(diǎn)的元素這種情形。所以屋摔，在一個(gè)大根堆中烁设，一個(gè)節(jié)點(diǎn)的元素在其子樹(shù)所有元素組成的集合中必定是最大值。這一結(jié)論至關(guān)重要钓试。
以下給出了兩個(gè)大根堆的示例：
元素下沉
在正式講解堆排序的實(shí)現(xiàn)步驟之前装黑，先說(shuō)一下十分有用的“元素下沉”方法，此方法可謂是堆排序的精華之所在弓熏。何為“元素下沉”恋谭？估計(jì)很少有人知道這個(gè)詞語(yǔ)的意思，不知道也沒(méi)關(guān)系挽鞠，因?yàn)檫@是我造的一個(gè)詞語(yǔ)...... :)疚颊，書(shū)本上有專(zhuān)門(mén)的詞匯，我覺(jué)得太過(guò)生硬信认，就自作主張起了一個(gè)別稱(chēng)材义，本文會(huì)一直沿用這個(gè)詞語(yǔ)。
給定一個(gè)完全二叉樹(shù)嫁赏，除了根節(jié)點(diǎn)以外其掂，此二叉樹(shù)滿(mǎn)足“堆序性”，“元素下沉”的目的是在此二叉樹(shù)中將根節(jié)點(diǎn)的元素放至合適的坑位潦蝇，相應(yīng)地調(diào)整其他元素清寇，最終使得包括根節(jié)點(diǎn)在內(nèi)的整棵二叉樹(shù)都滿(mǎn)足“堆序性”喘漏。
“元素下沉”的實(shí)施方案說(shuō)來(lái)也很簡(jiǎn)單：
1、當(dāng)父節(jié)點(diǎn)的元素值小于左子節(jié)點(diǎn)的元素值或者右子節(jié)點(diǎn)的元素值時(shí)华烟，將父節(jié)點(diǎn)的元素值與左右子節(jié)點(diǎn)較大的元素值進(jìn)行交換
2翩迈、針對(duì)交換后的父節(jié)點(diǎn)，循環(huán)執(zhí)行“元素下沉”操作
3盔夜、“元素下沉”的終止條件就是父節(jié)點(diǎn)的元素值不小于其任意左右子節(jié)點(diǎn)的元素值负饲，或者當(dāng)前父節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)（即當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)）。
以上給出了實(shí)施方案喂链，下面就直接貼出實(shí)現(xiàn)代碼（以整數(shù)序列為例）：
//給定父節(jié)點(diǎn)的索引返十，得到左子節(jié)點(diǎn)的索引
#define LeftChild(i) (2*(i)+1)
//元素下沉方法
void PercDown(int A[], int i, int N)
{
//子節(jié)點(diǎn)的索引號(hào)
int child;
//存儲(chǔ)當(dāng)前父節(jié)點(diǎn)元素的臨時(shí)變量
//(注：每一個(gè)節(jié)點(diǎn)都可以看作是其子樹(shù)的根節(jié)點(diǎn))
int tmp;
for (tmp = A[i]; LeftChild(i)<N; i = child)
{
child = LeftChild(i);
//挑選出左、右子節(jié)點(diǎn)中較大者
if (child != N-1 && A[child+1]>A[child])
{
child++;
}
//比較當(dāng)前父節(jié)點(diǎn)與較大子節(jié)點(diǎn)
if (A[i]<A[child])
{
//交換當(dāng)前父節(jié)點(diǎn)處的元素值與較大子節(jié)點(diǎn)的元素值
tmp= A[i];
A[i] = A[child];
A[child] = tmp;
}
else
{
break;
}
}
}
下面給出一個(gè)簡(jiǎn)單的示例來(lái)說(shuō)明“元素下沉”的過(guò)程：
原始二叉樹(shù)中椭微，除去根節(jié)點(diǎn)（元素1）洞坑，其子樹(shù)滿(mǎn)足堆序性，為了使得整棵完全二叉樹(shù)都滿(mǎn)足堆序性蝇率，需要為元素1找到合適的放置位置迟杂，并相應(yīng)地調(diào)整其它元素的位置。
實(shí)現(xiàn)此功能的對(duì)應(yīng)代碼為：
int A[] = {1,5,6,3,2,4};
PercDown(A, 0, 6);
第一次循環(huán)中本慕，根節(jié)點(diǎn)的元素1與左右子節(jié)點(diǎn)中較大的6進(jìn)行比較排拷，由于1<6,故1與6交換位置，第二次循環(huán)中锅尘，1與左右節(jié)點(diǎn)中較大的4進(jìn)行比較监氢，由于1<4,故1與4交換位置,又由于此時(shí)元素1作為當(dāng)前父節(jié)點(diǎn)時(shí)不存在左右子節(jié)點(diǎn)，故“元素下沉”操作到此結(jié)束藤违，最終得到一個(gè)具有堆序性的完全二叉樹(shù)浪腐。
堆排序的具體實(shí)現(xiàn)
下面開(kāi)始進(jìn)入正題了，堆排序算法究竟是怎么實(shí)現(xiàn)的呢顿乒？其實(shí)只需要簡(jiǎn)單的兩步就可以實(shí)現(xiàn)堆排序：
1）根據(jù)無(wú)序數(shù)組創(chuàng)建一個(gè)大根堆：自底向上遍歷 + 元素下沉
2）不斷調(diào)整大根堆牛欢，使其到達(dá)有序：互換 + 元素下沉
1）創(chuàng)建大根堆
給定了一個(gè)無(wú)序數(shù)組，用二叉樹(shù)的形式表現(xiàn)該數(shù)組時(shí)并不一定是大根堆淆游。比如
| 4 | 5 | 3 | 2 | 6 | 1 |
|---|
對(duì)應(yīng)的二叉樹(shù)為
不難發(fā)現(xiàn)此二叉樹(shù)不滿(mǎn)足“堆序性”傍睹。那么如何根據(jù)一個(gè)無(wú)序數(shù)組構(gòu)建一個(gè)大根堆呢？秘訣就在于上一節(jié)提到的“元素下沉”方法犹菱。
在此之前我們先來(lái)分析一下由無(wú)序數(shù)組構(gòu)建的二叉樹(shù)拾稳。仔細(xì)觀察可發(fā)現(xiàn)：僅僅考慮二叉樹(shù)中所有的葉子節(jié)點(diǎn)，它們必定是滿(mǎn)足“堆序性”的腊脱。
元素2访得、6、1已經(jīng)滿(mǎn)足了“堆序性”，故我們的目標(biāo)是調(diào)整剩余的父節(jié)點(diǎn)悍抑，使得整棵二叉樹(shù)都滿(mǎn)足“堆序性”鳄炉，最終構(gòu)建出一個(gè)大根堆。
俗話(huà)說(shuō)飯要一口一口的吃搜骡，構(gòu)建大根堆的過(guò)程亦然拂盯，在已經(jīng)滿(mǎn)足“堆序性”的元素集合中新增一個(gè)元素，采用“元素下沉”法進(jìn)行調(diào)整记靡，形成新的滿(mǎn)足“堆序性”的元素集合谈竿，在此基礎(chǔ)上再添加一個(gè)新的元素，并采用“元素下沉”法摸吠，如此循環(huán)空凸，直到所給無(wú)序數(shù)組的所有元素都滿(mǎn)足“堆序性”，則完成了大根堆的構(gòu)建寸痢。
下面結(jié)合實(shí)例進(jìn)行分析呀洲，目前已知元素2、6啼止、1滿(mǎn)足了堆序性道逗，在此基礎(chǔ)上添加元素3，二叉樹(shù)的形式表示為：
發(fā)現(xiàn)添加元素3后仍然滿(mǎn)足堆序性族壳，無(wú)需采用“元素下沉”法進(jìn)行調(diào)整。在此基礎(chǔ)上添加元素5趣些，表示為二叉樹(shù)的形式為：
發(fā)現(xiàn)引入元素5之后仿荆，破壞了“堆序性”。此時(shí)上一節(jié)討論的“元素下沉”法就能派上用場(chǎng)了坏平。還記得“元素下沉”法的應(yīng)用條件嗎? 除了根節(jié)點(diǎn)以外拢操，此二叉樹(shù)滿(mǎn)足“堆序性”,在這里就是指除了元素5以外，其他元素滿(mǎn)足 “堆序性”舶替。 這里調(diào)用一次“元素下沉”方法后得到的輸出結(jié)果為：
好的令境，到目前位置就差最后一個(gè)元素了。現(xiàn)在我們把元素4加入其中顾瞪，得到的二叉樹(shù)為：
很遺憾舔庶，添加元素4后導(dǎo)致整個(gè)二叉樹(shù)并不滿(mǎn)足“堆序性”，故又需要調(diào)用“元素下沉”方法對(duì)二叉樹(shù)進(jìn)行調(diào)整陈醒。調(diào)整的過(guò)程大致為：
至此惕橙，根據(jù)一個(gè)無(wú)序數(shù)組構(gòu)建大根堆的工作就完成了!
在這里需要說(shuō)明一點(diǎn)，給定一個(gè)無(wú)序數(shù)組钉跷，可以構(gòu)建出多個(gè)大根堆弥鹦，即其對(duì)應(yīng)的大根堆并不是唯一的。上述構(gòu)建方法只是構(gòu)建了其中的一個(gè)大根堆爷辙，我們的目的是構(gòu)建一個(gè)大根堆彬坏，具體是哪一個(gè)并無(wú)影響朦促。
以下給出了相同無(wú)序數(shù)組對(duì)應(yīng)的其他大根堆示例：
2）調(diào)整大根堆
得到了大根堆，我們的工作就完成了一半栓始。首先要思考一下為什么花了這么大力氣去構(gòu)建一個(gè)大根堆呢务冕？答案已經(jīng)呼之欲出了，沒(méi)錯(cuò)混滔，大根堆的根元素必然是整個(gè)堆中的最大值洒疚。
回到先前我們構(gòu)建的大根堆
不難發(fā)現(xiàn)根元素6正是最大值。好的坯屿，下面有個(gè)小技巧油湖，大家擦亮眼睛看好嘍~
沒(méi)錯(cuò)，就是將根節(jié)點(diǎn)元素與最后一個(gè)葉子節(jié)點(diǎn)的元素交換位置领跛，這樣做產(chǎn)生了兩個(gè)后果：1）最大值6被挑選出來(lái)乏德，并置于末位；2）根節(jié)點(diǎn)元素1打亂了“堆序性”吠昭。
對(duì)于第1）點(diǎn)喊括，正式我們所期望的，但是第2）點(diǎn)不是我們希望出現(xiàn)的結(jié)果矢棚，那該怎么呢郑什？此時(shí)又該“元素下沉”法出場(chǎng)了！目的是為了調(diào)整根節(jié)點(diǎn)元素1至合適的“坑位”蒲肋，使得二叉樹(shù)滿(mǎn)足“堆序性”蘑拯。 在這里需要說(shuō)明的一點(diǎn)是，由于元素6已經(jīng)確定為最大值兜粘，故此次可以不用參與“元素下沉”的過(guò)程申窘，即“元素下沉”只在以下二叉樹(shù)中開(kāi)展：
也就是說(shuō)元素6現(xiàn)在已經(jīng)被確定為最大值，沒(méi)有再與其他元素進(jìn)行比較的意義了孔轴。
以下為針對(duì)根節(jié)點(diǎn)元素1進(jìn)行“元素下沉”后的結(jié)果：
此時(shí)剃法，不考慮末位的元素6，二叉樹(shù)又滿(mǎn)足了“堆序性”Ｂ酚ァ（至此元素6將不參與任何“元素下沉”操作贷洲，元素6的位置已經(jīng)是最終的位置，因此后續(xù)討論的二叉樹(shù)可以將元素6排除在外晋柱！）
按照剛才的流程恩脂，我們把根節(jié)點(diǎn)元素，也就是當(dāng)前的最大值5與末位元素1進(jìn)行交換趣斤，再進(jìn)行“元素下沉”操作：
由此俩块，我們已經(jīng)得到了無(wú)序數(shù)組中最大的兩個(gè)值5、6，且他們均位于二叉樹(shù)的末尾處玉凯。后面的操作也都是在“首尾交換”势腮、“元素下沉”兩個(gè)操作中來(lái)回切換，直至所有元素全部變?yōu)橛行蛟芈停缦聢D所示：
將最終調(diào)整完成的二叉樹(shù)寫(xiě)成數(shù)組形式捎拯，可得到：
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|
可以看出，調(diào)整大根堆的過(guò)程就是自下而上循環(huán)進(jìn)行“首尾交換”和“元素下沉”操作的過(guò)程盲厌，目的只有一個(gè)：將較大元素調(diào)整至末位處署照！
至此，堆排序的工作全部完成吗浩，我們由一個(gè)無(wú)序數(shù)組建芙，經(jīng)過(guò)堆排序操作后得到了一個(gè)有序數(shù)組。
完整代碼
以上都側(cè)重于過(guò)程分析懂扼，下面給出堆排序的完整代碼(元素下沉方法前面已經(jīng)給出禁荸，這里不再重復(fù))：
//堆排序
void HeapSort(int A[], int N)
{
int i;
//步驟一：創(chuàng)建大根堆
for (i = N/2; i>=0; i--)
{
PercDown(A, i, N);
}
//步驟二：調(diào)整大根堆
for ( i = N-1; i > 0; i--)
{
//首尾交換
Swap(&A[0], &A[i]);
//元素下沉
PercDown(A, 0, i);
}
}
//交換兩個(gè)元素的位置
void Swap(int *num1, int * num2)
{
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
//主函數(shù)
void main()
{
int A[6] = {4,5,3,2,6,1};
HeapSort(A, 6);
}
運(yùn)行此代碼，數(shù)組A將由
| 4 | 5 | 3 | 2 | 6 | 1 |
|---|
調(diào)整為
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|
至此阀湿，講完赶熟！收工！陷嘴！
溫馨提示
本文一直在討論大根堆映砖，最后將數(shù)組調(diào)整為從小到大的順序。其實(shí)小根堆的實(shí)現(xiàn)原理和操作方法與大根堆完全一樣灾挨，只是大小順序的問(wèn)題邑退，大家有興趣也可以嘗試用小根堆實(shí)現(xiàn)排序，將無(wú)序數(shù)組調(diào)整為從大到小的順序涨醋！
python版完整代碼
def elementDown(self, A, start, end):
root_index = start
chid_index = 2 * start + 1 # 左子節(jié)點(diǎn)索引
while chid_index <= end:
if chid_index < end and A[chid_index] < A[chid_index + 1]:
chid_index += 1 # childNodeIndex代表右子節(jié)點(diǎn)索引
if A[chid_index] > A[root_index]:
# root ,child = child, root
A[chid_index], A[root_index] = A[root_index], A[chid_index]
root_index = chid_index
else:
break
chid_index = 2 * root_index + 1 # 左子節(jié)點(diǎn)索引
def heapSort(self, A):
n = len(A)
if n <= 1:
return A
# 創(chuàng)建大根堆
for i in range(n / 2, -1, -1): # 上層結(jié)點(diǎn)
self.elementDown(A, i, n - 1)
# 首尾互換瓜饥，元素下沉
for i in range(n - 1,-1,-1):
A[0], A[i] = A[i], A[0]
self.elementDown(A, 0, i - 1)
def sortIntegers2(self, A):
# write your code here
self.heapSort(A)
return A
