來征服資料結構與演算法吧 | 搞懂 Binary Heap 的排序原理
Hi！大家好，我是神 Q 超人！因為早早被叫起來掃墓，然後前兩天連假又把魔物獵人 Rise 打爆，現在沒什麼事情做，就來整理一下之前學過，但一直沒有時間打文章分享的 Binary Heap 的排序原理！ 🙌
Binary Heap
基本概念
Binary Heap 的概念是一個 Binary Tree（二元樹），也就是每一個數字下面最多只會有兩個數字，也有可能是一個或沒有。用圖來表示的話會長這樣子：
在上方的示意圖中，10 下方有 7 和 9，而 7 下方又有 2 和 1 兩個數字，雖然 9 下方只有一個 6，但仍然符合 Binary Tree 每個數字下都只會有兩個以下的數字的原則，也就是說如果 9 以下連 6 都沒有，也還是個 Binary Tree，只要不是三個或以上就好。
而 Binary Heap 的種類分成兩種，分別為 max-heap（最大堆積）和 min-heap（最小堆積），max-heap 就是所有數字都大於它之下的數字。像上方的示意圖，不論是 10 之下的 7 和 9、7 之下的 2 和 1 或者是 9 之下的 6，都沒有下方的數字比上方大的情況，所以就可以把上方的 Binary Heap 稱作 max-heap。另一方面，當所有的數字都比下方的數字要小時，則是 min-heap。
雖然上方都是以 Binary Tree 的結構來講解 Binary Heap，但 Binary Heap 可不是什麼新的資料結構，它也就只是個普通的 Array，只是用了 Binary Heap 的思維來處理排序。那 Binary Heap 的每個數字是怎麼對應到 Array 裡的呢？讓我們先看看一張圖：
上圖中的橘色字代表的是 index，雖然 Binary Heap 是個 Binary Tree，但是它在 Array 裡的位置會依照 Binary Heap 由上到下、從左到右做 index 的對應，而且我們還可以發現，在每一個 max-heap 的第一個 element（index 為 0 的數字） 都會是所有數字中最大的那個，因此只要我們不停的「用剩下的數字」完成 max-heap，那當比較完所有數字時，一個排序後的 Array 也就出現啦！
如何比較
這個部分會講解如何讓一個 Binary Tree 變成 max-heap 或是 min-heap，也是 Binary Heap 排序的重點和精華。假設我們有一個 Binary Tree：
第一步驟我們會從最後一個底下有數字的 index 開始比較，在上方的例子中就是 index 為 2 的數字 9 開始，畢竟如果從 index 為 5 的 6 開始一點意義都沒有，因為底下沒有任何數字可以比較。所以我們比較的順序就會是從 index 2 到 0。
那一開始取出 index 為 2 的 9 出來，讓它與下方的數字比較，這時候如果想要成為 max-heap 的話，那下方如果有數字比 9 大的那就要交換位置，而 9 下方只有一個較小的 6，因此不需要做處理。
接下來取出 index 為 1 的 7，我們可以發現 7 底下的右邊數字 10 比 7 還要大，而左邊的 2 又沒有比 10 大，因此 10 與 7 必須要交換位置：
再繼續比較前，先來觀察一下目前的 Binary Tree 已經比較過的部分，不論是 9 與底下的數字或是 10 與底下的數字，它們各自都成為了一個獨立的 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 的位置，所以會導致左邊底下的 max-heap 可能被破壞，因此必須要以原本 10 的那個位置（現在是數字 1）再去與下方做比較。1 先與右邊 7 做比較，再與左邊的 2 做比較，在這之中 7 會是最大的，因此 7 要與 1 換位置：
交換完後 1 下面也沒有其他數字了，所以也不用交換囉！
完成 max-heap / min-heap 之後
從倒數第二層開始，經過不斷的比較和交換位置一直到第一層，我們就可以得到一個 max-heap，也就是 index 為 0 的數是這堆數字中最大的一個，那接下來要如何排序出第二大的數字呢？
首先我們要把目前最大的數字和最右下的數字交換位置，以 index 來看的話就是把第一個數字移動到最後一個：
交換過後呢？我們就要忽略已經排序過的 10，並且用「剩下的數字」再做一次 max-heap：
即使少了 10，但經過比較後我們仍然會得到一個新的 max-heap，這時候在第一個位置上最大的數字是 9，因此 9 再與 Binary Heap 中最後一個數字 1 做交換：
接下來的步驟都一樣，忽略 9 和 10 用剩下的數字做 max-heap：
接著會得到剩下數字中最大的 7，然後把 7 和最後一個 1 做交換，再忽略 7、9 和 10，用剩下的數字形成 max-heap，一直到 Binary Heap 中沒有任何東西就代表排序完了（如果是 max-heap 最後會排序出由小到大的數字，min-heap 則是相反的由大到小）：
所以用 Binary Heap 做排序的過程就是一直找出最大或最小數，然後移動到當前這堆數字的最後一個，之後將它忽略再繼續尋找的過程。
除此之外還可以發現，因為我們每次都把最大的數字與最後一個數字交換，這會形成一個結果，那就是除了 index 為 0 的那個值之外，其他 index 與底下的數字一定還是維持著 max-heap 的 Binary Heap，大家可以滑上去確認一下，兩次把最大值換到 Binary Heap 內最後一個數字後都是這樣子。
所以如果我完成了一次 max-heap，那接下來的每一次，就不再需要從最後一個底下有數字的 index 開始形成 max-heap，只要從 index 0 開始執行就好。
把邏輯轉換成程式碼
以下的程式碼會以 max-heap 為例子，就像上方解釋原理的圖一一解說各個區塊的程式碼邏輯。
首先因為每個數字都要和底下的數字做比較，以形成一個個 max-heap，那既然 Binary Heap 的本體只是個 Array，又該如何知道每個 index 底下的 index 是多少呢？讓我們先來複習一下對照圖：
我們可以觀察到，如果我們把每個數字所在的 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 的數字）與 Binary Heap 中最後的數字交換，並且要忽略該數字，以 index 0 形成新的 max-heap，再交換、再忽略並以 index 0 形成新的 max-heap，一直到所有的數字都跑完才終止所有的排序，寫成程式碼的話邏輯如下：
首先是用迴圈跑 Array 內的所有數字，然後在第 4 行會把第一個數字和當前剩下數字的最後一個交換位置，例如第一次的時候，最大值要換到 Array 的最後一個，第二次的時候，最大值要換到 Array 的倒數第二個…依此類推，第 4 行就是再重現這個邏輯。
至於第 5 行就是從 index 0 的位置開始形成 max-heap，並且 Binary Heap 內的數字會越來越少，就是 nums.length - 2 - i 在控制的，第一次只需要忽略最後一個已交換到最後的最大值，所以忽略一個，第二次就是忽略兩個…等等，傳入 maxHeapify 的 size，這樣超過 size 的數字就不會加入比較，會直接被忽略。
等到所有的數字都比完，Array 也排序完囉！
參考資料
這個 Binary Heap 講解起來真的很辛苦（當初理解也花了很多時間 😂），不過在寫這篇文章的過程，因為想好好把每一個小步驟都解釋過一遍，現在也內化的差不多了！如果文章裡有任何問題或是錯誤的地方，再麻煩大家留言告訴我，非常感謝！任何回覆都很歡迎！ 🙌
