十大經(jīng)典排序之堆排序，被樹(shù)耽誤的數(shù)組
目錄
十大經(jīng)典排序算法江山圖
什么是堆？
定義
分類
作用
堆排序
算法描述
動(dòng)圖演示
圖解堆排序
代碼實(shí)現(xiàn)
穩(wěn)定性分析
時(shí)間復(fù)雜度分析
空間復(fù)雜度分析
十大經(jīng)典排序算法江山圖
堆排序在排序復(fù)雜性的研究中有著重要的地位，因?yàn)樗俏覀兯奈ㄒ荒軌蛲瑫r(shí)最優(yōu)的利用空間和時(shí)間的方法，當(dāng)空間十分緊張的時(shí)候（例如嵌入式系統(tǒng)或者低成本的移動(dòng)設(shè)備中）他很流行，因?yàn)樗挥脦仔芯湍軐?shí)現(xiàn)較好的性能。但是現(xiàn)代操作系統(tǒng)中很少使用他，因?yàn)樗麩o(wú)法利用緩存，這一點(diǎn)很致命。數(shù)組元素很少和相鄰的其他元素進(jìn)行比較，因此緩存未命中的次數(shù)要遠(yuǎn)遠(yuǎn)高于大多數(shù)比較都在相鄰元素間的算法，如快速排序，歸并排序，甚至是希爾排序。
什么是堆？
定義
?堆（英語(yǔ)：Heap）是計(jì)算機(jī)科學(xué)中的一種特別的完全二叉樹(shù)，滿足特性"給定堆中任意節(jié)點(diǎn)P和C，若P是C的母節(jié)點(diǎn)，那么P的值會(huì)小于等于（或大于等于）C的值"。?摘自維基百科。
?
首先堆是一個(gè)完全二叉樹(shù)（除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿的，最后一層的節(jié)點(diǎn)都靠左排列），這點(diǎn)很重要，直接決定了數(shù)組下標(biāo)和左右父節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系（關(guān)系往下看）。
分類
最小堆（min heap）：母節(jié)點(diǎn)的值恒小于等于子節(jié)點(diǎn)的值；
最大堆（max heap）：母節(jié)點(diǎn)的值恒大于等于子節(jié)點(diǎn)的值；
值得注意，這個(gè)地方對(duì)哦左右子節(jié)點(diǎn)的大小沒(méi)有要求。
而且，堆一般用數(shù)組來(lái)存儲(chǔ)，而不是樹(shù)。因?yàn)闃?shù)需要為其左右子節(jié)點(diǎn)分配指針空間，而數(shù)組使用數(shù)組下標(biāo)來(lái)表示左右子節(jié)點(diǎn)的位置，可以說(shuō)堆是被樹(shù)耽誤了的數(shù)組，頂著樹(shù)的光環(huán)成功勸退了一大批想學(xué)的人，結(jié)果實(shí)際上干著數(shù)組該干的事兒，算法史上最大的騙局，掛羊肉賣狗肉。
父節(jié)點(diǎn)和左右子節(jié)點(diǎn)在數(shù)組中的位置關(guān)系：
parent(i)?=?arr((i?-?1)/2)
left(i)???=?2i?+?1
right(i)??=?2i?+?2
作用
構(gòu)建優(yōu)先隊(duì)列 堆排序 找最值 你猜，面試官考你這個(gè)啥心態(tài)
值得注意，搜索不是堆的目的，并不是每一個(gè)最?。ù螅┒讯际且粋€(gè)有序數(shù)組！要將堆轉(zhuǎn)換成有序數(shù)組，需要使用堆排序，此處歡迎我們的堆排序隆重登場(chǎng)。
堆排序
正因?yàn)槎阎皇歉缸又g大小關(guān)系確定，左右子節(jié)點(diǎn)直接大小不確定，所以才要堆排序?qū)⑺械脑赜行蚺判颉?/p>
算法描述
以構(gòu)建大頂堆為例：
將待排序序列構(gòu)成一個(gè)大頂堆，此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)； 將其與末尾元素進(jìn)行交換，此時(shí)末尾就是最大值； 然后將剩余n-1個(gè)元素重新構(gòu)造成一個(gè)大頂堆，就會(huì)得到n個(gè)元素的次大值； 反復(fù)執(zhí)行前面2，3步，便能得到一個(gè)有序序列
動(dòng)圖演示
圖解堆排序
根據(jù)數(shù)組構(gòu)造大頂堆：
初始數(shù)組為：[6,1,2,3,0,4,5,7] 按照完全二叉樹(shù)，將數(shù)字依次填入，得到圖中第一幅圖; 從最下面的非葉子結(jié)點(diǎn)開(kāi)始(非葉子結(jié)點(diǎn)為 arr.length/2-1 = 8/2-1 =3，父節(jié)點(diǎn)是arr[0]，arr[3]也就是3)調(diào)整，根據(jù)性質(zhì)，左右子節(jié)點(diǎn)中小的數(shù)字往上移動(dòng)； 從下至上，從右往左，遞歸，直到根節(jié)點(diǎn)
構(gòu)造大頂堆
一次調(diào)整之后7成功上位，得到數(shù)組最大的值7，與此同時(shí)數(shù)組對(duì)應(yīng)的大頂堆構(gòu)造完成。
由下至上的堆有序化
這里可以看到，交換調(diào)整之后最大的元素到了最下面，最終會(huì)是越下面的數(shù)越大，因此構(gòu)造大頂堆得到的是降序，升序要構(gòu)造小頂堆。
代碼實(shí)現(xiàn)
import?com.sun.tools.javac.util.ArrayUtils;
/**
?*?@author?by?zengzhiqin
?*?2020-12-10
?*/
public?class?HeapSort?{
????public?static?int[]?heapSort?(int[]?arr)?{
????????if?(arr?==??null?&&?arr.length?==?0)?{
????????????throw?new?RuntimeException("數(shù)組不合法");
????????}
????????//?構(gòu)建堆（從最下面葉子結(jié)點(diǎn)層的上一層，即倒數(shù)第二層的第一個(gè)開(kāi)始進(jìn)行構(gòu)建調(diào)整）
????????for?(int?i?=?arr.length?/?2?-1;?i?>=?0;?i--)?{
????????????adjustDown(arr,?i,?arr.length);
????????}
????????//?循環(huán)調(diào)整下沉
????????for?(int?i?=?arr.length?-1;?i?>=?0;?i--)?{
????????????swap(arr,?0,?i);
????????????adjustDown(arr,?0,?i);
????????}
????????return?arr;
????}
????/**
?????*?調(diào)整
?????*?@param?arr
?????*?@param?parent
?????*?@param?length
?????*/
????public?static?void?adjustDown?(int[]?arr,?int?parent,?int?length)?{
????????//?臨時(shí)元素保存要下沉的元素
????????int?temp?=?arr[parent];
????????//?左節(jié)點(diǎn)的位置
????????int?leftChild?=?2?*?parent?+?1;
????????//?開(kāi)始往下調(diào)整
????????while?(leftChild?????????????//?如果右孩子節(jié)點(diǎn)比左孩子大，則定位到右孩子?(父節(jié)點(diǎn)只是比左右孩子都大，左右孩子大小不確定)
????????????if(leftChild?+?1?????????????????//?此時(shí)leftChild實(shí)際上是右孩子，但始終是左右里面最大的
????????????????leftChild?++?;
????????????}
????????????//??大頂堆條件被破壞了
????????????if?(arr[leftChild]?<=?temp)??{
????????????????break;
????????????}
????????????//?把子節(jié)點(diǎn)中大的值賦值給父節(jié)點(diǎn)
????????????arr[parent]?=?arr[leftChild];
????????????//?大的子節(jié)點(diǎn)為父節(jié)點(diǎn)，調(diào)整它的左右子節(jié)點(diǎn)
????????????parent?=?leftChild;
????????????leftChild?=?2?*?parent?+?1;
????????}
????????arr[parent]?=?temp;
????}
????/**
?????*?交換數(shù)組中兩個(gè)元素
?????*?@param?arr?數(shù)組
?????*?@param?i?父元素
?????*?@param?index?元素2
?????*/
????public?static?void?swap?(int[]?arr,?int?i,?int?index)?{
????????int?temp?=?arr[i];
????????arr[i]?=?arr[index];
????????arr[index]?=?temp;
????}
????public?static?void?main(String[]?args)?{
????????//int[]?arr?=?{5,?7,?8,?3,?1,?2,?4,?6,?8};
????????int[]?arr?=?{3,?1,?2,?4};
????????//int[]?arr?=?{1,?2,?3};
????????arr?=?heapSort(arr);
????????for?(int?i=0;?i????????????System.out.println(arr[i]);
????????}
????}
}
穩(wěn)定性分析
不穩(wěn)定。
時(shí)間復(fù)雜度分析
nlog(n)。
大頂堆構(gòu)造使用 O(N) 的時(shí)間，元素調(diào)整下濾需要 O(logN)，需要下濾 N-1 次，所以總共需要 O(N+(N-1)logN) = O(NlogN)。從過(guò)程可以看出，堆排序，不管最好，最壞時(shí)間復(fù)雜度都穩(wěn)定在O(NlogN)。
空間復(fù)雜度分析
原地排序，空間復(fù)雜度O(1)
參考資料：極客時(shí)間算法訓(xùn)練營(yíng)筆記，算法書(shū)籍