堆的介紹
實(shí)例問題：
如果需要在一堆數(shù)據(jù)里面，不斷提取，其中最大或最小的數(shù)據(jù)；
請(qǐng)問怎么實(shí)現(xiàn)？
實(shí)例分析：
可以使堆排序，實(shí)現(xiàn)上述功能：
堆是一個(gè)完全二叉樹；
對(duì)于堆來說，有大頂堆和小頂堆的區(qū)別；
大頂堆：根結(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)值，跟其他結(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)值比較，根結(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)值，最大，如下圖所示：
小頂堆：根結(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)值，跟其他結(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)值比較，根結(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)值，最小，如下圖所示：
雜論無章的完全二叉樹，構(gòu)造成大頂堆之后，如果要變成小頂堆，實(shí)現(xiàn)思路如下：
先將大頂堆的根結(jié)點(diǎn)，移到最下面；
然后將n-1個(gè)值，重新排序成大頂堆，移到最下面；
。。。。。。
移植n-1次，還剩一個(gè)值在最上面，作為根結(jié)點(diǎn)；
這就是小頂堆了。
代碼實(shí)現(xiàn)-大頂堆
首先，新建工程，如下圖所示：
參考配置工程參數(shù)，如下圖所示：
在主函數(shù)中，隨機(jī)定義一個(gè)數(shù)組，存儲(chǔ)幾組數(shù)據(jù)，如下圖所示：
定義大頂堆的排序方法，其中傳遞數(shù)組參數(shù)，如下圖所示：
因?yàn)椋幪?hào)最大的結(jié)點(diǎn)，肯定是葉子結(jié)點(diǎn)；
所以根據(jù)公式：左子結(jié)點(diǎn)是2i，右子結(jié)點(diǎn)是2i+1
最大編號(hào)的結(jié)點(diǎn)，對(duì)應(yīng)的父結(jié)點(diǎn)為：n/2=i，取商即可，忽略余數(shù)；
根據(jù)該父結(jié)點(diǎn)，同理，對(duì)應(yīng)父結(jié)點(diǎn)的父結(jié)點(diǎn)為：n/2=a，取商即可，忽略余數(shù)；
一直到，編號(hào)為1為止，如下圖所示：
然后，完成一次大頂堆的排序；
首先，設(shè)置max最大值，默認(rèn)為i；
根據(jù)公式，左子結(jié)點(diǎn)的編號(hào)，就是2i；右子結(jié)點(diǎn)的編號(hào)，就是2i+1；
如圖所示：
判斷，如果左子結(jié)點(diǎn)的編號(hào)值，小于最大編號(hào)值；如果左子結(jié)點(diǎn)，對(duì)應(yīng)的數(shù)據(jù)值，大于默認(rèn)的最大數(shù)據(jù)值；
將左子結(jié)點(diǎn)的編號(hào)值，賦值給，最大數(shù)據(jù)的編號(hào)值；
如下圖所示：
同理，判斷，如果右子結(jié)點(diǎn)的編號(hào)值，小于最大編號(hào)值；如果右子結(jié)點(diǎn)，對(duì)應(yīng)的數(shù)據(jù)值，大于默認(rèn)的最大數(shù)據(jù)值；
將右子結(jié)點(diǎn)的編號(hào)值，賦值給，最大數(shù)據(jù)的編號(hào)值；
如下圖所示：
判斷，max是否仍等于i；
max的默認(rèn)值是i，經(jīng)過比較后，如果max不等于i了，說明子結(jié)點(diǎn)對(duì)應(yīng)的值，比默認(rèn)的數(shù)據(jù)值大；
交換兩者的數(shù)據(jù)，如下圖所示：
完成一次，單獨(dú)的大頂堆排序。
對(duì)于堆排序來說，它們之間，是有嵌套關(guān)系的，如下圖所示：
如上圖所示，4和8、9可以構(gòu)成一個(gè)頂堆，2和4、5也可以構(gòu)成一個(gè)頂堆；
所以，它們之間，是存在嵌套關(guān)系的。
將代碼修改成while循環(huán)，針對(duì)嵌套進(jìn)行操作；
部分代碼，需要從while()中提取出來，需要另外定義一個(gè)tempd值，如下圖所示：
將判斷大小的關(guān)鍵代碼，搬移到while()死循環(huán)中，針對(duì)頂堆的嵌套，進(jìn)行操作；
完成一次max的選擇后，再重新對(duì)tempd賦值，再進(jìn)入while()循環(huán)，如下圖所示：
針對(duì)tempd操作，如果max=tempd，說明是子頂堆中的最大值；
這時(shí)，跳出判斷大小的while()函數(shù)即可，如下圖所示：
完成一次for循環(huán)后，就可以完成一次大頂堆的嵌套排序；
將該duiSort()函數(shù)，設(shè)置為，公有靜態(tài)函數(shù)，如下圖所示：
在主函數(shù)中，調(diào)用該方法，完成大頂堆的排序，如下圖所示：
遍歷輸出，大頂堆排序后的data數(shù)組，如下圖所示：
保存修改，按F5，運(yùn)行程序，如下圖所示：
大頂堆的代碼實(shí)現(xiàn)，測(cè)試成功。
