資料結構+算法（第10篇）叉堆“功夫熊貓”的速成之路

閱讀本文需要5分鐘

引言

上一篇文章《菜鳥也能“種”好二叉樹！》提到：樹是一種分層分類的資料結構，用途是查找和排序。而與查找和排序密切相關的就是求最值（最大值或者最小值）。今天我們就來介紹一個與最值相關的資料結構——二叉堆。

盡管網上或者相關的算法書均有對二叉堆算法的介紹，但大部分隻停留在how的階段，并未對一些關鍵細節進行why的深究。比如：

1. 為什麼二叉堆的算法都使用數組作為資料結構，而不是連結清單？
2. 為什麼要引入二叉堆的調整算法來構造堆？相對于插入法構造堆，為什麼更優？
3. 為什麼不論是調整法還是插入法來構造堆，都是自底向上進行周遊，而不是自頂向下？
4. 采用調整法來構造堆，為什麼時間複雜度是O(N)？

本文旨在填補這個空白，“授人魚更授人以漁”，讓你真正精通二叉堆，成為此領域的“功夫熊貓”！

二叉堆是個什麼鬼

二叉堆其實就是一種特殊的完全二叉樹，它實際上就是在完全二叉樹的定義上增加了一條規則：

若每個節點都比它的兩個子節點的值大，那麼這個完全二叉樹就是一個大頂堆；

若每個節點都比它的兩個子節點的值小，那麼這個完全二叉樹就是一個小頂堆。

圖1 大頂堆

圖2 小頂堆

二叉堆有什麼鬼用

根據上面大頂堆的定義，求一組元素的最大值，隻要我們能把這組元素按照大頂堆的形式組織起來，那麼根節點就是最大值所在的節點。

同理，求一組元素的最小值，隻要按照小頂堆的形式組織起來，那麼根節點就是最小值所在節點。

如何描述二叉堆

了解了堆有什麼用之後，接下來就要講如何來描述一個堆——換言之，堆的資料結構如何表達？

既然堆本質是完全二叉樹，是以堆也可以像完全二叉樹那樣，用連結清單或者數組來表達。唯一的差別是：在用連結清單或者數組來表達時，要時刻保證目前節點的值比兩子節點的值要大（或者小）。那麼實操時，如何做到這一點呢？

最樸素的想法就是：先對所有的元素進行排序，然後按照順序依次從根節點位置往下填。

且不談這個方法要涉及到全排序，耗時耗空間，它最大的問題是：

你都排好序了，那麼最值也就知道了，還跑回來構造個啥堆啊？

那麼還有什麼好方法呢？想想我們還有什麼武器沒有使用過？對了，還有在《再不會"降維打擊"你就Out了!》一文中提到的“核武器”——遞歸沒有使用呢！

遞歸構造二叉堆

為了簡化起見，下面我們以大頂堆為例，小頂堆可以對稱推導。

根據《再不會"降維打擊"你就Out了!》一文中講到的遞歸套路：

先分析規模因子：很明顯規模因子就是元素個數

再分析狀态轉移函數：假設構造規模為n-1的堆的算法是f(n-1)，那麼構造規模為n的堆，就相當于在f(n-1)的堆上插入第n個節點。如果設插入算法是g，那麼狀态轉移的表達式：

f(n)=g(f(n-1))           

複制

圖3 遞歸構造二叉堆

接下來看看初始問題狀态：顯然就是隻有一個元素的情況。

在看看邊界問題狀态：顯然就是一個元素都沒有的情況。

還是根據《神力加身！動态程式設計》和《史上最猛之遞歸屠龍奧義》中講到的老套路，看看能否用動态規劃來優化遞歸。

該問題的遞歸展開樹如下：

這種簡單結構應用自底向上的動态規劃不要太爽：）

先用插入算法g()生成一個節點的堆、再疊加用一次g()生成兩個節點的堆，以此類推，直到生成覆寫所有節點的堆。

經過上面的分析，可以看出：遞歸構造堆的核心在于堆的插入算法。

連結清單 vs. 數組

既然要向已有堆插入新節點，那麼首先要定位插入的位置。

最樸素的想法就是：從根節點開始，逐層依次比較各節點，精确找到插入的位置。

圖4 插入新節點——廣度周遊二叉堆

圖5 插入新節點——廣度周遊二叉堆

圖6 插入新節點——廣度周遊二叉堆

這其實就是所謂的“廣度優先周遊算法”。

插入之後，原有節點的坑被新元素占了，它就隻能去占子節點的坑了，這種“霸占”行為逐層傳導下去，直到原葉子節點隻能委屈求全再向下挪一層——“打不過你，我跑總可以了吧”。

看到這裡似乎一切都很美好，但是這裡有兩個問題：

第一：在圖6的廣度周遊中，如何從值為20的節點跳到值為3的節點？

如果整棵樹是用連結清單形式來存儲各節點的話：

由于值為3的節點不是值為20的節點的子節點，從值為20的節點根本無法直接得知值為3的節點的位置，除非回溯到值為9的節點，用值為9的節點的子節點連結才能抵達值為3的節點。根據在《史上最猛之遞歸屠龍奧義》一文中學到的知識，這個回溯需要用到堆棧。不僅需要額外的存儲空間，而且也耽誤時間。

第二：如果隻是逐一下挪，那麼産生的新二叉樹，可能都不是一棵完全二叉樹了（如圖5所示），也就不符合堆的定義。此時可能還需要進行水準調整。想想這個過程就很複雜。

那麼往下挪會破壞完全二叉樹的結構，是否可以向上挪呢？

圖7 二叉堆的後插

如圖7所示，如果将新節點插入到完全二叉樹的“尾部”（值為13的節點），那麼向上逐層比較、進行必要位置調換，就可以完美避開上述的第二個問題。

這個新方法的關鍵在于：

（1）識别出完全二叉樹的“尾部”位置

（2）向上回溯的連結資訊

對于第（2）點，采用雙向連結清單就可以解決；但是對于第（1）點就比較麻煩。

除了上圖這種一般情況外，還有下圖這種滿二叉樹的情況。不同的情況，“尾部”位置并不是固定的，有時在靠近樹的右邊，有時在靠近樹的左邊。

圖8 二叉堆的後插

因為沒有現成的資料結構或者特征能辨別“尾部”位置，需要開發相應算法來解決。這個算法我們留在下一篇文章詳細來講。

綜上所述，用連結清單來描述堆不友善。

如果整棵樹是用數組形式來存儲各節點的話，看看解決上面兩個問題是否友善。

在圖7所示的一般完全二叉樹中，除開待插入的值為8的節點，節點總數為12。插入位置是值為13的節點位置。用數組存儲時，值為13的節點是數組的第6号元素。6=12/2。

在圖8所示的滿二叉樹中，除待插入的值為8的節點之外，節點總數為15。插入位置是值為1的節點位置。用數組存儲時，值為1的節點是數組的第8号元素。8=15/2的值向上取整。

看出什麼規律了嗎？

無論是一般完全二叉樹還是滿二叉樹，插入的位置都可以由數組元素總數唯一決定！

這個規律其實隐含在上一篇文章《菜鳥也能“種”好二叉樹！》的推論5.2.1中：

數組第n号元素所代表的節點，它的左子節點是數組的第(2n+1)号元素，它的右子節點是數組的第2(n+1)号元素

用floor_round(a)表示對a向下取整的話，那麼把上面推論反過來用就是：

數組第n号元素所代表的節點，它的父節點是數組的第floor_round(n/2)号元素。

當n可被2整除時，說明第n号元素所代表的節點是其父節點的左孩子；

當n不被2整除時，說明第n号元素所代表的節點是其父節點的右孩子。

這樣，我們就完美地解決了問題（1）。

至于問題（2），對數組就更不是問題了——還記得《小白也能玩轉數組和連結清單啦！》一文中的比喻嗎？數組就是電梯，電梯既可以上也可以下！

堆的插入算法

看到這裡，相信最大堆的插入算法已經一目了然了：

注意：為了友善地利用上述父子元素的序号關系，我們把數組的第一個下标空出來不放實際元素，隻作為一個臨時單元使用。

import java.util.ArrayList;
class BinaryHeap {
 private ArrayList arrayNodes;
 public BinaryHeap() {
 this.arrayNodes=new ArrayList(1);
 }
 
 public void heapInsert(int newItem) {
 int count=this.arrayNodes.size();
 if(count<=1) {
 this.arrayNodes.add(newItem);
 return;
 }
 int i=count>>1;
 this.arrayNodes.add(newItem);
 int j=count;
 do {
 this.arrayNodes.set(0,this.arrayNodes.get(i));
 
 if((int)(this.arrayNodes.get(0))<newItem) {
 this.arrayNodes.set(i, newItem);
 this.arrayNodes.set(j, this.arrayNodes.get(0));
 j=i;
 i=i>>1;
 }
 else {
 break;
 }
 }while(i>0);
 }
}           

複制

有了堆的插入算法，根據前面的分析，循環對節點調用heapInsert()就可以生成完整的堆。

堆的構造算法的時間複雜度

顯然，有多少個元素，就需要調用多少次heapInsert()。

heapInsert()本身的時間複雜度f與while循環執行的次數有關。很顯然，最壞情況下，while循環的次數就是堆（完全二叉樹）的高度H。

根據上一篇《菜鳥也能“種”好二叉樹！》中講到的二叉樹的性質：

H=up_round(log(M+1))=O(logM)，其中M是目前堆中的節點總數。

設最終堆的節點總數為N，則M從1變化到N。

設堆的構造算法的時間複雜度為K，則根據《KO！大O——時間複雜度》一文的推論3.1有：

K=O(log1)+O(log2)+……+O(logN)
 =O(log1+log2+……+logN)
 =O(log1x2x……xN)
 =O(logN!)<O(logN^N)=O(NlogN)（式1）           

複制

還能更快嗎？

整個算法的主體是heapInsert()，對它分析如下：

（1）每個新節點都要挨個與“尾部”到堆頂這條路徑上的每個節點做比較；

（2）每個節點必然和它子樹中的所有節點進行過比較

圖9 二叉堆節點插入算法分析

圖10 二叉堆節點插入算法分析

圖11 二叉堆節點插入算法分析

将節點A被比較的總次數記為C(A)，則：

C(A)=A的子樹節點總數M(A)（式2）           

複制

顯然假設最終二叉堆由n個節點構成，則總比較次數N為：

N=C(A1)+C(A2)+...+C(An)
 =M(A1)+M(A2)+...+M(An)（式3）           

複制

顯然這個過程是應該被優化的——如果每個節點不用和它子樹中的所有節點進行比較，算法速度不就提升了嗎？

那麼如何減少這個比較次數呢？

上面算法是将節點一個一個地往數組裡添加調整，那麼如果把所有節點一次性全部扔進數組進行調整，是否就可以達到這個目的呢？

全部扔進數組後，相當于一次性建立了一個完全二叉樹，現在開始對其進行調整。

調整動作涉及兩方面：

（1）調整的方向

（2）要調整的節點

自頂向下調整 vs. 自底向上調整

調整方向到底采用自頂向下還是自底向上呢？

根據《神力加身！動态程式設計》一文所講到的，為了利用動态規劃，最好采用自底向上。

為了證明這個預判是正确的，我們作如下分析。

假設我們采用自頂向下的調整政策，那麼會遭遇下圖13~圖15所示的“回溯”問題，而破壞遞歸下降的過程。

如下圖所示，如果子樹裡有值非常大的節點，那麼這個節點最終不僅僅是取代其父節點位置，它還要“篡位”祖父節點甚至曾祖父節點！

圖13 二叉堆自頂向下調整分析

圖14 二叉堆自頂向下調整分析

圖15 二叉堆自頂向下調整分析

一旦發生上述的“回溯”，那麼就會帶來兩方面問題：

（1）算法邏輯的複雜性增加；

（2）根據《史上最猛之遞歸屠龍奧義》一文所提到的，回溯就要用堆棧來防止“失憶”，這會增加存儲的開銷。

自頂向下的遞歸式調整算法如下：

public void heap_fixdown_recursive(int index, int[] arrayNodes) {
 if(arrayNodes==null) {
 return;
 }
 int count=arrayNodes.length-1;
 if(index<=0||index>count) {
 return;
 }
 int left_index=index<<1;
 int right_index=left_index+1;
 
 boolean left_valid=(left_index<=count)?true:false;
 boolean right_valid=(right_index<=count)?true:false;
 heap_fixdown_recursive(right_index, arrayNodes);
 if(right_valid) {
 heap_fixdown_recursive(left_index, arrayNodes);
 }
 int current=arrayNodes[index];
 int left=left_valid?arrayNodes[left_index]:0;
 int right=right_valid?arrayNodes[right_index]:0;
 int max=left_valid?left:0;
 
 if(right_valid&&right>max) {
 max=right;
 }
 if(left_valid) {
 if(max>current) {
 if(max==left) {
 arrayNodes[left_index]=current;
 arrayNodes[index]=max;
 heap_fixdown_recursive(left_index, arrayNodes);
 }
 else if(right_valid){
 arrayNodes[right_index]=current;
 arrayNodes[index]=max;
 heap_fixdown_recursive(right_index, arrayNodes);
 }
 }
 }
 }
 public void heapBuild_recursive(int[] list_nodes) {
 if(list_nodes==null) {
 return;
 }
 if(list_nodes.length<=1) {
 return;
 }
 heap_fixdown_recursive(1, list_nodes);
 }           

複制

二叉堆調整算法

既然有了上述的遞歸算法，那麼按照《史上最猛之遞歸屠龍奧義》一文介紹的“人肉消除遞歸”套路，可以輕松寫出對應的非遞歸算法。

下面我們換個角度、“一題多解”，看看能不能直接用動态規劃來推出非遞歸算法。

自底向上調整關鍵就是以下幾點：

（1）自底向上，先将父節點的左右子樹調整成堆；

（2）再來比較父節點與其孩子的值：如果目前父節點的值小于孩子的值，那麼就交換兩者的位置，将父節點下推。

先來分析一下自底向上調整的軌迹：

圖16 二叉堆自底向上調整算法

圖17 二叉堆自底向上調整算法

上圖中紫色箭頭表示向上調整的軌迹。可以看出：

（1）整個軌迹分為兩個次元——垂直次元和水準次元。

垂直次元：方向向上。紫色箭頭表示向上調整到父節點一層；

水準次元：方向向左。紫色箭頭表示向左調整到相鄰的兄弟節點。

（2）每一層水準方向的周遊距離=對應父子節點在數組中的下标之差。

（3）由于對目前節點下推之後，要能傳回到之前的位置繼續向上調整，是以需要記憶傳回位置。這個已經老生常談多次，用堆棧保留即可。其實從《史上最猛之遞歸屠龍奧義》一文中講到的遞歸消除技巧也可以推導出來這個結論：

畫出上面遞歸式二叉堆調整算法的遞歸展開樹如下，遞歸實作體中有3個子遞歸調用：

圖18 遞歸展開樹

根據《史上最猛之遞歸屠龍奧義》一文中講到的：為了差別子遞歸調用傳回時的“微觀位址”，需要增加标記儲存到堆棧中。

由前一章節的結論：父節點在數組中的下标=子節點在數組中的下标/2。

根據上面的分析（1）和（2），可以得出如下的堆調整算法與優化後的堆構造算法：

public void heap_fixdown_nonrecursive(int[] arrayNodes) {
 if(arrayNodes==null) {
 return;
 }
 int count=arrayNodes.length;
 if(count<=1) {
 return;
 }
 int index=count-1;
 while(index>1) {
 int layer_cursor=index>>1;
 while(index>layer_cursor) {
 //swap father and child if the value of child is bigger
 int father_index=index>>1;
 int left_index=father_index<<1;
 int right_index=left_index+1;
 while(left_index<count) {
 int left=arrayNodes[left_index];
 int father=arrayNodes[father_index];
 int max=left;
 int push_down_start_index=-1; 
 
 if(right_index<count) {
 int right=arrayNodes[right_index];
 if(right>max) {
 max=right;
 }
 }
 if(max>father) {
 if(max==left) {
 arrayNodes[left_index]=father;
 arrayNodes[father_index]=max; 
 push_down_start_index=left_index;
 }
 else {
 arrayNodes[right_index]=father;
 arrayNodes[father_index]=max; 
 push_down_start_index=right_index;
 }
 }
 //Push down father node
 if(push_down_start_index!=-1) {
 father_index=push_down_start_index;
 left_index=father_index<<1;
 right_index=left_index+1;
 }
 else {
 break;
 } 
 }
 father_index=index>>1;
 index-=2;
 }
 index=layer_cursor;
 } 
 }
 public void heapBuild_nonrecursive(int[] list_nodes) {
 if(list_nodes==null) {
 return;
 }
 if(list_nodes.length<=1) {
 return;
 }
 heap_fixdown_nonrecursive(list_nodes);
 }           

複制

通過堆調整算法來構造堆的時間複雜度

從上面的堆調整算法可以看出，在最壞情況下：

高度為h的每個節點k都被進行了如下操作：

1. 左右孩子做了一次比較
2. 該節點與孩子中最大的那個做了一次比較
3. 交換父子節點位置
4. 下推到葉子節點

其中第1步和第2步都是1個簡單的比較語句，第3步涉及一次交換，第4步共需要做(H-h)次交換（設H是整個二叉堆的高度），是以對于節點k的時間開銷為O(H-h)。

設高度h的節點數目為m，則:

h<H時：m=2^(h-1)
h=H時：1<=m<=2^(h-1)（式4）           

複制

高度h的所有節點的建構時間開銷為

mxO(H-h)=O(m(H-h))（式5）           

複制

若設M=葉子節點總數，則M<=2^(H-1)，整個二叉堆建構的時間複雜度K為：

K=O(2^(1-1)x(H-1))+O(2^(2-1)x(H-2))+...O(2^(h-1)x(H-h))+...+O(Mx(H-H))
 <=O(2^(1-1)x(H-1))+O(2^(2-1)x(H-2))+...O(2^(h-1)x(H-h))+...+O(2^(H-1)x(H-H))
 =O(2^(1-1)x(H-1)+2^(2-1)x(H-2)+...+2^(H-1)x(H-H))
 =O(H(2^0+2^1+...+2^(H-1))-(1x2^0+2x2^1+...+Hx2^(H-1)))（式6）           

複制

令s=2^0+2^1+...+2^(H-1)，t=1x2^0+2x2^1+...+Hx2^(H-1)，則上式簡記為：

K<=O(Hxs-t)（式7）           

複制

s是一個等比數列求和，其值：

s=2^H-1（式8）           

複制

t式右邊可寫成如下形式：

[1^2^0+1x2^1+1x2^2+...+1x2^(H-1)]
 +[1x2^1+1x2^2+...+1x2^(H-1)]
 +[1x2^2+...+1x2^(H-1)]
 +...
 +[1x2^(H-1)]           

複制

每個中括号裡都是一個等比數列，其值分别是2^H-2^0，2^H-2^1，...，2^H-2^(H-1），是以：

t=(2^H-2^0)+(2^H-2^1)+...+(2^H-2^(H-1))
 =(2^H+2^H+...+2^H)-(2^0+2^1+...+2^(H-1))           

複制

上式第一個括号裡共有H個2^H，其值等于Hx2^H；

上式第二個括号裡是一個等比數列，其值等于2^H-1。是以：

t=Hx2^H-(2^H-1)
 =1-2^H+Hx2^H（式9）           

複制

将式8、式9代入式7可得：

K<=O(sH-t)
 =O(Hx(2^H-1)-(1-2^H+Hx2^H)
 =O(2^H-H-1)（式10）           

複制

根據《菜鳥也能“種”好二叉樹！》的5.1章節的結論：

H<=logN（N代表二叉堆的節點總數）（式11）           

複制

代入式10可得：

K<=O(2^logN-logN-1)
 =O(N-logN-1)
 =O(N)（式12）           

複制

這表示：通過堆調整算法來構造堆的時間複雜度為O(N)，僅僅與元素數目線性相關。

Top N問題

求最大值時，構造大頂堆，堆頂就是最大值；

求最小值時，構造小頂堆，堆頂就是最小值。

求次大（小）值時，可以将堆頂元素拿走，再把最後一個元素換到堆頂，從堆頂進行調整，調整結束後的堆頂就是次大（小）值。

依次類推，可以求出Top N元素。

One More Thing

筆者原創連載《算法素顔》這個系列的目的就是：打消一些朋友對算法高深莫測的印象，還原算法的本質。“素顔”一詞源自日語，意為“本質、真面目”。

現在很多朋友學習算法的動機在于求職應聘找高薪，為了追求短時間的速成，大量地刷題。其實這并不是真正提高算法素養的正道。

這種方式相當于将自己退化成機器，采用機器學習的強化學習算法——利用海量的刷題來“喂資料”。但是人相對于機器，高明之處在于通過少量樣本、進行深度思考，直接發現本質的規律，進而舉一反三、擴大應該用邊界，效率高下之分立竿見影。

後面筆者會寫一篇文章，詳細來講講學習算法的“正确姿勢”。

結束