內(nèi)容來(lái)自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會(huì)偶爾插入自己的注釋和理解，盡量會(huì)完成作業(yè)

本次作業(yè)是自己能夠?qū)懗龆雅判虻拇a，我是自己看著自己寫的總結(jié)寫出來(lái)的

第11章 樹結(jié)構(gòu)實(shí)際應(yīng)用

11.1堆排序

11.1.1堆排序的基本介紹

1.????? 堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時(shí)間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序。

2.????? 堆是具有以下性質(zhì)的完全二叉樹:每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值，稱為大頂堆，注意︰沒(méi)有要求結(jié)點(diǎn)的左孩子的值和右孩子的值的大小關(guān)系。

3.????? 每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值，稱為小頂堆

4.????? 大頂堆舉例說(shuō)明

5.????? 小頂堆舉例說(shuō)明

6.一般升序采用大頂堆，降序采用小頂堆

11.1.2堆排序基本思想

堆排序的基本思想是:

1.????? 將待排序序列構(gòu)造成一個(gè)大頂堆

2.????? 此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。

3.????? 將其與末尾元素進(jìn)行交換，此時(shí)末尾就為最大值。

4.????? 然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)堆，這樣會(huì)得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了。

可以看到在構(gòu)建大頂堆的過(guò)程中，元素的個(gè)數(shù)逐漸減少，最后就得到一個(gè)有序序列了

11.1.3堆排序步驟圖解說(shuō)明

要求:給你一個(gè)數(shù)組{4,6,8,5,9}，要求使用堆排序法，將數(shù)組升序排序。

步驟一構(gòu)造初始堆。將給定無(wú)序序列構(gòu)造成一個(gè)大頂堆(一般升序采用大頂堆 ,降序采用小頂堆)。

1)???? 假設(shè)給定無(wú)序序列結(jié)構(gòu)如下

2)???? 此時(shí)我們從最后一個(gè)非葉子結(jié)點(diǎn)開始(葉結(jié)點(diǎn)自然不用調(diào)整，第一個(gè)非葉子結(jié)點(diǎn)arr.length/2-1=5/2-1=1，也就是下面的6結(jié)點(diǎn)），從左至右，從下至上進(jìn)行調(diào)整。

3)???? 找到第二個(gè)非葉節(jié)點(diǎn)4，由于[4,9,8]中9元素最大，4和9交換。

4)???? 這時(shí)，交換導(dǎo)致了子根[4,5,6]結(jié)構(gòu)混亂，繼續(xù)調(diào)整，[4,5,6]中6最大，交換4和6

此時(shí)，我們就將一個(gè)無(wú)序序列構(gòu)造成了一個(gè)大頂堆。

步驟二：將堆頂元素與末尾元素進(jìn)行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進(jìn)行交換、重建、交換。

1.???? 將堆頂元素9和末尾元素4進(jìn)行交換

2.???? 重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義

3.???? 再將堆頂元素8與未尾元素5進(jìn)行交換，得到第二大元素8

4.???? 后續(xù)過(guò)程，繼續(xù)進(jìn)行調(diào)整，交換，如此反復(fù)進(jìn)行，最終使得整個(gè)序列有序

再簡(jiǎn)單總結(jié)下堆排序的基本思路∶

1).將無(wú)序序列構(gòu)建成一個(gè)堆，根據(jù)升序降序需求選擇大頂堆或小頂堆;

2).將堆頁(yè)元素與末尾元素交換，將最大元素"沉"到數(shù)組末端;

3).重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整+交換步驟，直到整個(gè)序列有序。

11.1.4堆排序代碼實(shí)現(xiàn)

要求:給你一個(gè)數(shù)組{4,6,8,5,9}，要求使用堆排序法，將數(shù)組升序排序。代碼實(shí)現(xiàn):看老師演示:

說(shuō)明:

1.???? 堆排序不是很好理解，老師通過(guò)Debug幫助大家理解堆排序

2.???? 堆排序的速度非?？?，在我的機(jī)器上8百萬(wàn)數(shù)據(jù)3秒左右。O(nlogn)

代碼實(shí)現(xiàn)