點(diǎn)擊藍(lán)色字關(guān)注我們！

什么是堆

「堆」首先是一個(gè)完全二叉樹，「堆」分為「大頂堆」和「小頂堆」；
「大頂堆」 :
每個(gè)節(jié)點(diǎn)的值大于或等于其左右孩子節(jié)點(diǎn)的值，稱為大頂堆。
「小頂堆」同理就是每個(gè)節(jié)點(diǎn)的值小于或等于其左右孩子節(jié)點(diǎn)的值。
「注意」:
每個(gè)節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)的大小關(guān)系并沒有限定。

大頂堆舉例

如圖：

大頂堆舉例

首先其為一個(gè)完全二叉樹，且其每個(gè)節(jié)點(diǎn)的值都大于或者等于其左右孩子節(jié)點(diǎn)的值。
完全二叉樹從上到下，從左到右依次編號，就可以將其進(jìn)行順序存儲，我們從根節(jié)點(diǎn)開始，從0開始編號，存入數(shù)組如下：

大頂堆存入數(shù)組舉例

堆特點(diǎn)

由大頂堆定義知道，如果我們從上到下，從左到右，根節(jié)點(diǎn)開始從0編號進(jìn)行順序存儲的話，并將數(shù)組記為arr；
我們可以得到如下式子：
arr[i] >= arr[ 2i + 1] ?&& arr[ i ] >= arr[ 2i + 2];
其中 2i + 1為第 i 個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的編號。2i + 2為第 i 個(gè)節(jié)點(diǎn)的右孩子節(jié)點(diǎn)的編號；
同理得小頂堆的特點(diǎn)：
arr[i] <= arr[ 2i + 1] ?&& arr[ i ] <= arr[ 2i + 2];

堆排序基本思想

本文以大頂堆為例，進(jìn)行講解。
算法步驟如下：
1、首先將待排序序列構(gòu)建成一個(gè)大頂堆(存入數(shù)組中)，那么這時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)；
2、將堆頂元素與最后一個(gè)元素交換，那么末尾元素就存入了最大值；
3、將剩余的 n - 1個(gè)元素重新構(gòu)建成一個(gè)大頂堆，重復(fù)上面的操作；
反復(fù)執(zhí)行，就能得到一個(gè)有序序列了。

舉例

給定一個(gè)待排序序列數(shù)組 arr = [ 0 , 2, ?4, ?1 , 5 ]；
先構(gòu)建成一個(gè)完全二叉樹如下;

初始狀態(tài)

構(gòu)建堆

「我們從最后一個(gè)非葉子節(jié)點(diǎn)開始，從左至右，從下到上，開始調(diào)整」；
最后一個(gè)非葉子節(jié)點(diǎn)的索引即 arr.length / 2向下取整 - 1 ，對于此例就是 5 / 2向下取整 - 1 = 2 - 1 = 1；
即值為2的節(jié)點(diǎn)；

構(gòu)建堆1

我們用左右孩子節(jié)點(diǎn)的最大值與該節(jié)點(diǎn)進(jìn)行比較；
此時(shí)我們發(fā)現(xiàn)它的左右孩子節(jié)點(diǎn)的最大值為5，大于2，進(jìn)行交換；

構(gòu)建堆2

然后處理下一個(gè)非葉子節(jié)點(diǎn)，即剛才的索引減去1；1 - 1 = 0；
即：

構(gòu)建堆3

左右孩子節(jié)點(diǎn)為5和4，5最大，且大于該節(jié)點(diǎn)的值，發(fā)生交換；

構(gòu)建堆4

這時(shí)我們發(fā)現(xiàn)了一個(gè)問題:
「值為0的節(jié)點(diǎn)的左右節(jié)點(diǎn)又比該節(jié)點(diǎn)大了，又不滿足大頂堆的定義了」

繼續(xù)進(jìn)行調(diào)整:

構(gòu)建堆5

對非葉子節(jié)點(diǎn)調(diào)整完畢，構(gòu)建大頂堆完成。

交換

將堆頂元素與末尾元素進(jìn)行交換，使得末尾元素最大。

堆頂元素與末尾元素交換

當(dāng)交換完畢后最大的元素已經(jīng)到達(dá)數(shù)組末尾；

第一次交換后

對數(shù)組中其他元素進(jìn)行排序即可。

剩下的四個(gè)元素進(jìn)行調(diào)整

進(jìn)行交換：

第二大元素歸位

剩下的元素調(diào)整并交換后：

第三大元素歸位

剩下的元素調(diào)整并交換后：

第三大元素歸位第四大元素歸位置

此時(shí)也意味著排序完成了。

代碼

先說下調(diào)整的代碼；
我們需要三個(gè)參數(shù)，待排序的數(shù)組，數(shù)組的長度，還有一個(gè)就是調(diào)整的哪一個(gè)非葉子節(jié)點(diǎn)；

?/***?author:微信公眾號:code隨筆*?@param?arr?待排序的數(shù)組*?@param?i???表示等待調(diào)整的哪個(gè)非葉子節(jié)點(diǎn)的索引*?@param?length?待調(diào)整長度*/public?static?void?adjustHeap(int?arr[],int?i,int?length){//非葉子節(jié)點(diǎn)的值int?notLeafNodeVal?=?arr[i];//k的初始值為當(dāng)前非葉子節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的索引//k?=?2?*?k?+?1表示再往左子節(jié)點(diǎn)找for(int?k?=?i?*?2?+?1;k<length;k=2?*k?+?1){//如果k?+?1還在待調(diào)整的長度內(nèi)，且右子樹的值大于等于左子樹的值//將k++，此時(shí)為當(dāng)前節(jié)點(diǎn)的右孩子節(jié)點(diǎn)的索引if(k+1<length?&&?arr[k]?<?arr[k+1]){k++;}//如果孩子節(jié)點(diǎn)大于當(dāng)前非葉子節(jié)點(diǎn)if(arr[k]?>?notLeafNodeVal){arr[i]?=?arr[k];//將當(dāng)前節(jié)點(diǎn)賦值為孩子節(jié)點(diǎn)的值i?=?k;//將i賦值為孩子節(jié)點(diǎn)的值，再看其孩子節(jié)點(diǎn)是否有比它大的}else{break;//能夠break的保證是，我們是從左至右，從下到上進(jìn)行調(diào)整的//只要上面的不大于，下面的必不大于}}//循環(huán)結(jié)束后，將i索引處的節(jié)點(diǎn)賦值為之前存的那個(gè)非葉子節(jié)點(diǎn)的值arr[i]?=?notLeafNodeVal;}

再說下堆排序代碼,看好注釋；

//堆排序方法public?static?void?heapSort(int?arr[]){//進(jìn)行第一次調(diào)整for(int?i=arr.length/2?-?1;i>=0;i--){adjustHeap(arr,i,arr.length);}for(int?j=arr.length?-?1;j>0;j--){//進(jìn)行交換int?temp?=?arr[j];arr[j]?=?arr[0];arr[0]?=?temp;//調(diào)整長度為j的那些//這里為什么填0呢//因?yàn)槲覀兊谝淮握{(diào)整的時(shí)候從左到右，從下到上調(diào)整的；//交換時(shí)只是變動(dòng)了堆頂元素和末尾元素//末尾元素我們不用去管，因?yàn)橐呀?jīng)是之前長度最大的了//只需要把當(dāng)前堆頂元素找到合適的位置即可adjustHeap(arr,0,j);}}

完整代碼

import?java.util.Arrays;public?class?Solution?{public?static?void?main(String[]?args)?{int?[]?arr?=?new?int[]{0?,?2,??4,??1?,?5};heapSort(arr);System.out.println(Arrays.toString(arr));}//堆排序方法public?static?void?heapSort(int?arr[]){//進(jìn)行第一次調(diào)整for(int?i=arr.length/2?-?1;i>=0;i--){adjustHeap(arr,i,arr.length);}for(int?j=arr.length?-?1;j>0;j--){//進(jìn)行交換int?temp?=?arr[j];arr[j]?=?arr[0];arr[0]?=?temp;//調(diào)整長度為j的那些//這里為什么填0呢//因?yàn)槲覀兊谝淮握{(diào)整的時(shí)候從左到右，從下到上調(diào)整的；//交換時(shí)只是變動(dòng)了堆頂元素和末尾元素//末尾元素我們不用去管，因?yàn)橐呀?jīng)是之前長度最大的了//只需要把當(dāng)前堆頂元素找到合適的位置即可adjustHeap(arr,0,j);}}/***?author:微信公眾號:code隨筆*?@param?arr?待排序的數(shù)組*?@param?i???表示等待調(diào)整的哪個(gè)非葉子節(jié)點(diǎn)的索引*?@param?length?待調(diào)整長度*/public?static?void?adjustHeap(int?arr[],int?i,int?length){//非葉子節(jié)點(diǎn)的值int?notLeafNodeVal?=?arr[i];//k的初始值為當(dāng)前非葉子節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的索引//k?=?2?*?k?+?1表示再往左子節(jié)點(diǎn)找for(int?k?=?i?*?2?+?1;k<length;k=2?*k?+?1){//如果k?+?1還在待調(diào)整的長度內(nèi)，且右子樹的值大于等于左子樹的值//將k++，此時(shí)為當(dāng)前節(jié)點(diǎn)的右孩子節(jié)點(diǎn)的索引if(k+1<length?&&?arr[k]?<?arr[k+1]){k++;}//如果孩子節(jié)點(diǎn)大于當(dāng)前非葉子節(jié)點(diǎn)if(arr[k]?>?notLeafNodeVal){arr[i]?=?arr[k];//將當(dāng)前節(jié)點(diǎn)賦值為孩子節(jié)點(diǎn)的值i?=?k;//將i賦值為孩子節(jié)點(diǎn)的值，再看其孩子節(jié)點(diǎn)是否有比它大的}else{break;//能夠break的保證是，我們是從左至右，從下到上進(jìn)行調(diào)整的//只要上面的不大于，下面的必不大于}}//循環(huán)結(jié)束后，將i索引處的節(jié)點(diǎn)賦值為之前存的那個(gè)非葉子節(jié)點(diǎn)的值arr[i]?=?notLeafNodeVal;} }

時(shí)間復(fù)雜度

在建初始堆時(shí)，其復(fù)雜度為;
交換操作需 n-1 次;
重建堆的過程中近似為；
堆排序時(shí)間復(fù)雜度為。

穩(wěn)定性

堆排序是不穩(wěn)定的：
比如：10，9，6，9；如圖：

穩(wěn)定性分析用圖

當(dāng)堆頂元素10和末尾元素交換后，兩個(gè)9的相對位置發(fā)生改變。

已發(fā)布：

【算法知識】詳解冒泡算法

【算法知識】詳解選擇排序算法

【算法知識】詳解插入排序算法

【算法知識】詳解快速排序算法

【算法知識】詳解基數(shù)排序算法

往期精彩回顧適合初學(xué)者入門人工智能的路線及資料下載機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印機(jī)器學(xué)習(xí)在線手冊深度學(xué)習(xí)筆記專輯AI基礎(chǔ)下載（pdf更新到25集）機(jī)器學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)專輯本站qq群1003271085，加入微信群請回復(fù)“加群”獲取一折本站知識星球優(yōu)惠券，復(fù)制鏈接直接打開：https://t.zsxq.com/yFQV7am喜歡文章，點(diǎn)個(gè)在看

總結(jié)

以上是生活随笔為你收集整理的【算法知识】详解堆排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。