來征服資料結構與演算法吧| 搞懂Binary Heap 的排序原理

而Binary Heap 的種類分成兩種，分別為max-heap（最大堆積）和min-heap（最小堆積），max-heap 就是所有數字都大於它之下的數字。

像上方的示意圖，不論是 ... GetunlimitedaccessOpeninappHomeNotificationsListsStoriesWritePublishedinStarbugsWeekly星巴哥技術專欄來征服資料結構與演算法吧|搞懂BinaryHeap的排序原理PhotobyMarkusSpiskeonUnsplashHi！大家好，我是神Q超人！因為早早被叫起來掃墓，然後前兩天連假又把魔物獵人Rise打爆，現在沒什麼事情做，就來整理一下之前學過，但一直沒有時間打文章分享的BinaryHeap的排序原理！🙌BinaryHeap基本概念BinaryHeap的概念是一個BinaryTree（二元樹），也就是每一個數字下面最多只會有兩個數字，也有可能是一個或沒有。

用圖來表示的話會長這樣子：BinaryTree在上方的示意圖中，10下方有7和9，而7下方又有2和1兩個數字，雖然9下方只有一個6，但仍然符合BinaryTree每個數字下都只會有兩個以下的數字的原則，也就是說如果9以下連6都沒有，也還是個BinaryTree，只要不是三個或以上就好。

而BinaryHeap的種類分成兩種，分別為max-heap（最大堆積）和min-heap（最小堆積），max-heap就是所有數字都大於它之下的數字。

像上方的示意圖，不論是10之下的7和9、7之下的2和1或者是9之下的6，都沒有下方的數字比上方大的情況，所以就可以把上方的BinaryHeap稱作max-heap。

另一方面，當所有的數字都比下方的數字要小時，則是min-heap。

雖然上方都是以BinaryTree的結構來講解BinaryHeap，但BinaryHeap可不是什麼新的資料結構，它也就只是個普通的Array，只是用了BinaryHeap的思維來處理排序。

那BinaryHeap的每個數字是怎麼對應到Array裡的呢？讓我們先看看一張圖：BinaryHeap與Array的對照上圖中的橘色字代表的是index，雖然BinaryHeap是個BinaryTree，但是它在Array裡的位置會依照BinaryHeap由上到下、從左到右做index的對應，而且我們還可以發現，在每一個max-heap的第一個element（index為0的數字）都會是所有數字中最大的那個，因此只要我們不停的「用剩下的數字」完成max-heap，那當比較完所有數字時，一個排序後的Array也就出現啦！如何比較這個部分會講解如何讓一個BinaryTree變成max-heap或是min-heap，也是BinaryHeap排序的重點和精華。

假設我們有一個BinaryTree：未排序過的BinaryTree第一步驟我們會從最後一個底下有數字的index開始比較，在上方的例子中就是index為2的數字9開始，畢竟如果從index為5的6開始一點意義都沒有，因為底下沒有任何數字可以比較。

所以我們比較的順序就會是從index2到0。

那一開始取出index為2的9出來，讓它與下方的數字比較，這時候如果想要成為max-heap的話，那下方如果有數字比9大的那就要交換位置，而9下方只有一個較小的6，因此不需要做處理。

接下來取出index為1的7，我們可以發現7底下的右邊數字10比7還要大，而左邊的2又沒有比10大，因此10與7必須要交換位置：數字10與7交換位置再繼續比較前，先來觀察一下目前的BinaryTree已經比較過的部分，不論是9與底下的數字或是10與底下的數字，它們各自都成為了一個獨立的max-heap：比較過的數字都變成max-heap了代表我們每次比較的過程，都會讓該index以下的的數字變成max-heap，也就是說，讓一堆數字變成max-heap的過程，就等於是在尋找該數字中的最大值。

等到倒數第二層的數字都比完後，就會把層數往上移，剛剛倒數第二層比較的index是2和1，而再往上那層就只剩下index為0的1了，我們的步驟和之前一樣，先把1和底下右邊的9去比，發現9會比1還要大，但是1底下還有左邊的數字10，而10又比9更大，所以要與1換位置的並不是9，而是10：10與1交換排序這時候有個地方要注意，因為我們交換了10和1的位置，所以會導致左邊底下的max-heap可能被破壞，因此必須要以原本10的那個位置（現在是數字1）再去與下方做比較。

1先與右邊7做比較，再與左邊的2做比較，在這之中7會是最大的，因此7要與1換位置：7與1交換位置交換完後1下面也沒有其他數字了，所以也不用交換囉！完成max-heap/min-heap之後從倒數第二層開始，經過不斷的比較和交換位置一直到第一層，我們就可以得到一個max-heap，也就是index為0的數是這堆數字中最大的一個，那接下來要如何排序出第二大的數字呢？首先我們要把目前最大的數字和最右下的數字交換位置，以index來看的話就是把第一個數字移動到最後一個：目前最大值移動到最右下方的位置（以index來看就是第一個與最後一個交換）交換過後呢？我們就要忽略已經排序過的10，並且用「剩下的數字」再做一次max-heap：忽略10，用剩下的數字做max-heap即使少了10，但經過比較後我們仍然會得到一個新的max-heap，這時候在第一個位置上最大的數字是9，因此9再與BinaryHeap中最後一個數字1做交換：把最大的9和BinaryTree中最後一個數字交換接下來的步驟都一樣，忽略9和10用剩下的數字做max-heap：忽略9和10做max-heap接著會得到剩下數字中最大的7，然後把7和最後一個1做交換，再忽略7、9和10，用剩下的數字形成max-heap，一直到BinaryHeap中沒有任何東西就代表排序完了（如果是max-heap最後會排序出由小到大的數字，min-heap則是相反的由大到小）：最後會被忽略的數字，也就是已經排序過後的Array了所以用BinaryHeap做排序的過程就是一直找出最大或最小數，然後移動到當前這堆數字的最後一個，之後將它忽略再繼續尋找的過程。

除此之外還可以發現，因為我們每次都把最大的數字與最後一個數字交換，這會形成一個結果，那就是除了index為0的那個值之外，其他index與底下的數字一定還是維持著max-heap的BinaryHeap，大家可以滑上去確認一下，兩次把最大值換到BinaryHeap內最後一個數字後都是這樣子。

所以如果我完成了一次max-heap，那接下來的每一次，就不再需要從最後一個底下有數字的index開始形成max-heap，只要從index0開始執行就好。

把邏輯轉換成程式碼以下的程式碼會以max-heap為例子，就像上方解釋原理的圖一一解說各個區塊的程式碼邏輯。

首先因為每個數字都要和底下的數字做比較，以形成一個個max-heap，那既然BinaryHeap的本體只是個Array，又該如何知道每個index底下的index是多少呢？讓我們先來複習一下對照圖：BinaryHeap和Array的對照圖我們可以觀察到，如果我們把每個數字所在的index，分別做index*2+1和index*2+2，就剛好會得到底下左邊或右邊數字的index，所以待會我們就要把要比較的index與index*2+1和index*2+2三個數字去比大小，把最大的數字和index換位置就對了，然後記得沒換的話沒事，但如果換的話，要再接著檢查下方被交換的index的max-heap有沒有被破壞掉。

知道數字要和誰比較後，就接著來說怎麼找到最後一個底下有數字的index吧！只需要用倒推法就好！因為我們已經知道底下的數字分別為index*2+1和index*2+2，換句話說，最後一個數字的index一定是某個數字的index*2+1或index*2+2。

舉例來說上圖的Array有6個數字，所以最後一個數字的index是5，我們就可以利用5扣掉2或1再除上2以得到它上方數字的index，那要扣掉1還是2呢？我們可以試著想，如果扣1的話我們就是預設它是底下左邊的數字，所以如果是右邊數字被扣1就會多了0.5，因此要扣1後除於2再做無條件捨去。

另一方面如果扣2的話我們就是當他是底下右邊的數字，在這情況下如果是左邊的數字就會少0.5，所以要無條件進位。

好的，那知道從哪裡比較就可以來寫個什麼了，首先是從最後一個底下有數字的index開始，把整個Array變成max-heap：上方的maxHeapify就是負責比較當前和底下的左右數字，如果有比較大的話，那就要取出較大的那個換位置，然後換位置後又要確認在它之下的max-heap有沒有被破壞，所以要用被替換的位置再執行一次maxHeapify。

至於第三個參數size是為了控制已排序過的數字，再第二次開始需要忽略它們時就會使用到。

然後下方的迴圈就是從最後一個底下有數字的index開始跑迴圈執行maxHeapify，一直到index變成0為止。

我有在幾個關鍵處下console.log，有興趣可以看一下比較和交換的過程：比較和交換的過程都會和上方的圖解一模一樣喲在形成一次max-heap後，我們需要把當前的最大值（index為0的數字）與BinaryHeap中最後的數字交換，並且要忽略該數字，以index0形成新的max-heap，再交換、再忽略並以index0形成新的max-heap，一直到所有的數字都跑完才終止所有的排序，寫成程式碼的話邏輯如下：首先是用迴圈跑Array內的所有數字，然後在第4行會把第一個數字和當前剩下數字的最後一個交換位置，例如第一次的時候，最大值要換到Array的最後一個，第二次的時候，最大值要換到Array的倒數第二個…依此類推，第4行就是再重現這個邏輯。

至於第5行就是從index0的位置開始形成max-heap，並且BinaryHeap內的數字會越來越少，就是nums.length-2-i在控制的，第一次只需要忽略最後一個已交換到最後的最大值，所以忽略一個，第二次就是忽略兩個…等等，傳入maxHeapify的size，這樣超過size的數字就不會加入比較，會直接被忽略。

等到所有的數字都比完，Array也排序完囉！參考資料https://alrightchiu.github.io/SecondRound/comparison-sort-heap-sortdui-ji-pai-xu-fa.html#heapify這個BinaryHeap講解起來真的很辛苦（當初理解也花了很多時間😂），不過在寫這篇文章的過程，因為想好好把每一個小步驟都解釋過一遍，現在也內化的差不多了！如果文章裡有任何問題或是錯誤的地方，再麻煩大家留言告訴我，非常感謝！任何回覆都很歡迎！🙌MorefromStarbugsWeekly星巴哥技術專欄一群技術人想要寫出一些好文章所建立的技術專欄。

每週二一篇原創文章、一封電子報，歡迎大家訂閱！主網站：https://weekly.starbugs.dev/。

ReadmorefromStarbugsWeekly星巴哥技術專欄AboutHelpTermsPrivacyGettheMediumappGetstarted神Q超人1.94KFollowers82年次，單純相信努力不會騙人FollowMorefromMediumkhushieadvaniLeetCode1324.PrintWordsVerticallyUsingTypeScript/JavaScriptRafaelHovhannisyanDomain-SpecificTypesforPrimitivesMartinaBabinskaRomantoIntegerinTypescript(again :))SharmishthaDhuriTypescriptfortherescueHelpStatusWritersBlogCareersPrivacyTermsAboutKnowable