【考試向】資料結構筆記（堆積樹）

歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～

堆積（Heap）

定義

堆積是一棵二元樹，定義如下：

必為一棵完整二元樹（Complete Binary Tree）
- 所謂完整（Complete）：除了最底層之外，上面每一層的節點都必須是填滿的，而且最底層的節點，必須由左至右依序填入，中間不能有空缺。
- 為什麼這樣規定？因為這樣的結構非常緊湊，可用一維陣列來做儲存，而不用指標（Pointers），在記憶體管理和讀取速度上非常有效率。
必須滿足堆積性質（Heap Property）
- 根據節點數值的大小關係，Heap 主要分為兩種：
  1. 最大堆（Max-Heap）：任何一個父節點的值，都 $\ge$ 其子節點的值，表示整棵樹的根節點（Root）一定會是這棵樹中的最大值。
  2. 最小堆（Min-Heap）：任何一個父節點的值，都 $\le$ 其子節點的值，表示整棵樹的根節點（Root）一定會是這棵樹中的最小值。

調整 Heap

假設以下操作都是以最大堆（Max-Heap）來做，即父節點必須 $\ge$ 子節點（數字越大的地位越高）。

1. 由下而上調整（Sift-Up / Bubble-Up）

這個操作主要發生在新增節點（Insert）時。

當一個新節點加入 Heap 時，為了維持完整二元樹的緊湊結構，只能先把它排在陣列的最尾端（整棵樹的最底層、最右邊的位置）。

但新節點的數值可能很大，如果把它留在那裡，就破壞了最大堆積的規定，所以它必須由下而上去比較、換位置對調。

找出父節點：假設新節點現在位於陣列的索引值 $i$ ，它的父節點位在 $(i - 1) / 2$ 。
向上比較：將新節點的值與父節點比較。
對調（Swap）：
- 如果新節點 $>$ 父節點，交換位置（新節點往上爬一層）。
- 如果新節點 $\le$ 父節點，停止對調。
上述步驟重複直到新節點 $\le$ 父節點。

2. 由上而下調整（Sift-Down / Bubble-Down / Heapify）

這個操作主要發生在取出根節點或是將無序陣列建構堆積（Build-Heap）時。

新節點的初始位置會在根節點，數值通常會很小，因此必須向下比較、對調位置。

找出子節點：假設索引值為 $i$ ，兩個子節點分別在 $2i + 1$ （左子節點）和 $2i + 2$ （右子節點）。
向下比較（找數值大的）：先比較左、右兩個子節點，找出數值比較大的那一個。
對調：
- 如果目前節點 $<$ 子節點，交換位置。
- 如果目前節點 $\ge$ 子節點，停止對調。
上述步驟重複直到目前節點 $\ge$ 子節點。

比較表

特性	由下而上（Sift-Up）	由上而下（Sift-Down）
常見觸發時機	新增資料（Insert）	取出極值或建立堆積（Heapify）
移動方向	從葉節點往根節點攀升	從根節點往葉節點沉降
比較對象	只需和一個父節點比較	必須先在兩個子節點中找最大／小者，再與之比較
時間複雜度	最差 $O(log n)$	最差 $O(log n)$

Heap 加入操作

同樣假設現在是最大堆積的情形。

標準的執行步驟：

先加在陣列最尾端：將新元素直接放到陣列的最後一個位置，可確保它仍是一棵完整二元樹。
由下而上（Sift-Up）調整：讓新元素與父節點比較，如果比父節點大，就互換位置，一路往上直到比父節點小為止。

舉例：假設目前有一個 Max-Heap 陣列：[40, 30, 15, 10, 20]，如圖：

現在要加入數字 50：

放尾端：把 50 加到陣列最後面。
- 陣列變成：[40, 30, 15, 10, 20, 50]。
- 50 現在在索引值 5 的位置（也就是 15 的左子節點）。
Sift-Up 第一次比較：50 的父節點是 15（索引值 2），50 > 15，直接互換。
- 陣列變成：[40, 30, 50, 10, 20, 15]
Sift-Up 第二次比較：50 現在在索引值 2，其新父節點是 40（索引值 0），50 > 40，再互換。
- 陣列變成：[50, 30, 40, 10, 20, 15]
結束：50 已成為根節點（索引值 0），沒有父節點了。

圖解：

Heap 刪除操作

再次強調，現在同樣假設最大堆積。

觀念釐清：在 Heap 的常規操作中，刪除通常專指取出並刪除根節點（最大值或最小值）。Heap 這種資料結構天生就不適合用來隨機尋找並刪除中間的某個特定數字（要找特定數字，二元搜尋樹 BST 會更適合）。

標準執行步驟：

取出根節點：把陣列索引值 0 的元素拿走（這就是我們所要的最大值），此時樹的頂端破了一個洞。
填坑：把陣列中最後一個元素（最底層最右邊的葉節點）拔起來，直接塞到根節點的空缺處，並把陣列長度減一。
做由上而下（Sift-Down）的 Heap 調整。

舉例：假設目前有一個 Max-Heap 陣列：[50, 30, 40, 10, 20, 15]，如圖：

取出根節點：把 50 拿走。
最後的做遞補：把陣列最後一個數字 15 移到根節點位置，並移除陣列最後一個位子。
- 陣列變成：[15, 30, 40, 10, 20]
Sift-Down 第一次比較：
- 15 坐在根節點（索引 0），其子節點是 30 和 40。
- 30 < 40，選擇 40 跟 15 對調。
- 陣列變成：[40, 30, 15, 10, 20]
Sift-Down 第二次比較：
- 15 現在在索引值 2，計算其子節點位置 2*2+1 = 5。
- 但目前陣列最大索引值只有 4，表示 15 已經掉到底層（成為葉節點），因此結束。

圖解：

Heap 練習題：調整、加入、刪除

調整這棵樹成 max-heap：

調整方式：

min-heap 最小堆

先前說明的 Heap 皆為最大堆（max-heap），有 max-heap 一定會有 min-heap。

Min-Heap 同樣是一棵完整二元樹，但它的數值條件剛好與 Max-Heap 相反：

任何一個父節點的值，都必須 $\le$ 其左右子節點的值。
整棵樹的根節點（Root），一定會是所有資料中的最小值。

Min-Heap 是 Heap 非常重要的性質，可用於實作 Dijkstra 最短路徑演算法。

如何將二元樹調整成 min-heap

逐一插入法（Sift-Up）

作法：把原本的陣列當成一堆還沒處理的積木，準備一個全新的空 Heap，接著把數字一個一個丟進去，每次丟進去都執行上一篇提到的由下而上（Sift-Up）動作。

流程：

插入 40（Sift-Up）
插入 50（Sift-Up）
插入 10（Sift-Up）… 依此類推。

時間複雜度：每次插入最差是 $O(\log N)$ ，總共執行 $N$ 次，所以總時間複雜度為 $O(N \log N)$ 。

標準建構法 / 陣列原地調整（Sift-Down）

這是最聰明，也是標準函式庫（如 C++ 的 std::make_heap）所採用的方法，其想法為：不要從頭建一棵樹，而是從現有的樹由下而上把壞掉的節點修好。

只需用到由上而下（Sift-Down）的技巧，而且不需要檢查所有的節點。

作法：

找到這棵樹的最後一個非葉節點，如果陣列長度是 $n$ ，這個節點的索引值必定是 $(n/2) - 1$ （向下取整數）。
從這個節點開始，一路往回（往索引值 0 的方向），對每一個節點做 Sift-Down。
注意：因為現在是 Min-Heap，Sift-Down 的規則是找出左右子節點中較小的那一個，如果父節點比它大，就互換位置。

Sift-Down 範例

現在有個陣列：[40, 50, 10, 30, 20]，轉成二元樹後會是：

索引 0：40（左右子為 50, 10）
索引 1：50（左右子為 30, 20）
索引 2, 3, 4：分別是 10, 30, 20（葉節點）

尋找起點：最後一個非葉節點索引是 $(5/2) - 1 = 1$ ，即數字 50。
處理索引 1（數字 50）：
- 50 的子節點是 30 和 20。
- 最小的子節點是 20。
- 因為 50 > 20，因此兩者交換，陣列變成 [40, 20, 10, 30, 50]。

處理索引 0（數字 40）：
- 往回走來到根節點，40 的子節點現在是 20 和 10。
- 最小的子節點是 10。
- 40 > 10，交換，陣列變成 [10, 20, 40, 30, 50]。

40 被換到了索引 2 的位置，它是葉節點，因此 Sift-down 結束。

最終陣列為 [10, 20, 40, 30, 50]，已是一棵 Min-Heap。

時間複雜度： $O(N)$ 。

min-heap 的加入刪除操作範例

min-heap 的加入刪除操作與 max-heap 差不多，甚至可以說完全一樣的，接下來就直接進到範例。

假設目前有一個已經建好的 Min-Heap [10, 20, 15, 40, 50, 30, 25]，二元樹結構如下：

根節點：10
10 的子節點：20（左）, 15（右）
20 的子節點：40（左）, 50（右）
15 的子節點：30（左）, 25（右）

現在要加入節點 12，要求出加入後的 min-heap 長怎樣：

放到最尾端：將 12 加到陣列最後面。
- 目前陣列：[10, 20, 15, 40, 50, 30, 25, 12]
- 12 現在在索引值 7 的位置，其父節點是索引值 $(7-1)/2 = 3$ 的 40。

第一次比較（Sift-Up）：
- 比較 12 與父節點 40。
- 因為 12 < 40，交換。
- 陣列變成：[10, 20, 15, 12, 50, 30, 25, 40]

第二次比較（Sift-Up）：
- 12 現在來到索引值 3，它的新父節點是索引值 1 的 20。
- 比較 12 與父節點 20。
- 因為 12 < 20，交換。
- 陣列變成：[10, 12, 15, 20, 50, 30, 25, 40]

第三次比較（Sift-Up）：
- 12 現在來到索引值 1，父節點是根節點 10。
- 比較 12 與 10，12 > 10，停止交換，加入完畢。

接著延續上面處理好的例子，現在要刪除根節點 10（刪除用 sift-down），目前的陣列是：[10, 12, 15, 20, 50, 30, 25, 40]。

拿走 10，把最後一個數字 40 搬到最前面。
- 陣列變成：[40, 12, 15, 20, 50, 30, 25]

第一次比較（Sift-Down）：
- 40 在根節點（索引 0），子節點是 12 和 15。
- 找出數字最小的子節點 12。
- 比較 40 與 12，因為 40 > 12，交換。
- 陣列變成：[12, 40, 15, 20, 50, 30, 25]

第二次比較（Sift-Down）：
- 40 掉到了索引 1，其新子節點是 20 和 50。
- 找出最小的子節點 20。
- 比較 40 與 20，因為 40 > 20，交換。
- 陣列變成：[12, 20, 15, 40, 50, 30, 25]

結束：40 掉到了索引 3，沒有子節點了（成為葉節點）。

min-max heap

min-max heap 是結合了 min-heap、max-heap 兩者而來的，適合需要同時快速取得最大值與最小值的情況，例如雙端優先佇列（Double-Ended Priority Queue）。

其定義在於層級交替（Alternating Levels）的特性：

樹的每一層會被交替指定為 Min 層 或 Max 層。

Min 層（Min Level）：位於偶數深度（Depth 0, 2, 4…），在此層的任何節點，其值必須是以該節點為根的子樹中最小的。
- 根節點（Root，位於 Depth 0）永遠在 Min 層，因此整棵樹的最小值必然在根節點 $A[1]$ （假設起始索引在 1）。
Max 層（Max Level）：位於奇數深度（Depth 1, 3, 5…），在此層的任何節點，其值必須是以該節點為根的子樹中最大的。
- 整棵樹的最大值必然是根節點的子節點之一，也就是 $A[2]$ 或 $A[3]$ （若樹的大小 $\ge 2$ ）。

這種結構讓尋找最小值與最大值的時間複雜度都是 $O(1)$ 。

註：Min 層、Max 層都要各自遵守 min-heap 與 max-heap 的規則。（在 Min 層遵守的是 min-heap，Max 層遵守 max-heap）

min-max heap 的加入操作

將新元素加入 Min-Max Heap 的時間複雜度為 $O(\log n)$ ，該加入操作稱為 Bubble Up（向上浮動）。

執行步驟：

放置元素：將新元素 $X$ 放在陣列的最後一個位置（維持完整二元樹的形狀）。
確認層級與父節點：檢查 $X$ 的父節點 $P$ 。
判斷與交換：
- 如果 $X$ $X$ 位於 Min 層：
  - 若 $X > P$ ：違反了 Max 層父節點 $P$ 必須大於所有子孫的規則，因此將 $X$ 與 $P$ 交換，接著讓 $X$ 在 Max 層的祖先中繼續 Bubble Up Max。
  - 若 $X \le P$ ：沒有違反父節點規則，直接讓 $X$ 在 Min 層的祖先中繼續 Bubble Up Min。
- 如果 $X$ $X$ 位於 Max 層：
  - 若 $X < P$ ：違反了 Min 層父節點 $P$ 必須小於所有子孫的規則，將 $X$ 與 $P$ 交換，接著讓 $X$ 在 Min 層的祖先中 Bubble Up Min。
  - 若 $X \ge P$ ：沒有違反規則，直接讓 $X$ 在 Max 層的祖先中 Bubble Up Max。

Bubble Up 怎麼做？

以 Bubble Up Min 為例：

檢查 $X$ 的祖父節點 $GP$ （同為 Min 層）。
如果 $X < GP$ ，則將 $X$ 與 $GP$ 交換，並繼續以 $GP$ 的位置向上檢查祖父節點，直到不需交換或到達根節點為止。

min-max heap 加入操作範例

建立一棵包含 7 個節點的 Min-Max Heap，陣列表示為 [10, 50, 40, 20, 30, 35, 15]（索引從 1 開始）。

樹狀結構如下：

假設現在要將節點 12 加入，則將其加入到陣列最後方：

12 的父節點是 20（Min 層）。

因為 12 位於 Max 層，如果其在 Min 層的父節點（20） > 12，則違反 Min 層父節點應小於子孫的規則，因此 12 與 20 交換。

現在 12 位於 Min 層，此時要檢查其祖父節點（同樣在 Min 層的 10），由於 12 < 10，因此停止 Bubble up，加入操作完成。

min-max Heap 的刪除操作

刪除操作分為刪除最小值（Delete Min）與刪除最大值（Delete Max），兩者的時間複雜度皆為 $O(\log n)$ ，該刪除操作的概念稱為 Trickle Down（向下過濾）。

刪除最小值（Delete Min）：最小值一定在根節點 $A[1]$ $A [1]$ 。
- 執行步驟：
  1. 取出根節點的值（即最小值）。
  2. 將陣列最後一個元素 $X$ 移到根節點 $A[1]$ ，並將 Heap 的大小減 1。
  3. 對根節點執行 Trickle Down 讓 $X$ $X$ 找到正確的位置：
    - 找出 $X$ 的所有子節點與孫節點中，值最小的一個節點 $M$ 。
    - 如果 $M$ $M$ 是 $X$ $X$ 的子節點：
      - 若 $X > M$ ，則交換 $X$ 與 $M$ 。
    - 如果 $M$ $M$ 是 $X$ $X$ 的子孫節點：
      - 若 $X > M$ ，則交換 $X$ 與 $M$ 。
      - 接著檢查交換後 $X$ （目前在 $M$ 的位置）與其現在的父節點 $P$ ，因為 $M$ 在 Min 層， $P$ 在 Max 層，如果 $X > P$ ，則交換兩者。
      - 繼續以 $M$ 的位置對 $X$ 執行 Trickle Down 遞迴向下處理。
刪除最大值（Delete Max）：最大值必定是根節點的子節點 $A[2]$ $A [2]$ 或 $A[3]$ $A [3]$ 中較大的那一個。
- 執行步驟：
  1. 比較 $A[2]$ 與 $A[3]$ ，找出最大值的索引（假設為 $K$ ）。
  2. 取出 $A[K]$ 的值。
  3. 將陣列最後一個元素 $Y$ 移到 $A[K]$ 的位置，並將 Heap 的大小減 1。
  4. 對位置 $K$ 執行 Trickle Down Max，在此的邏輯與 Delete Min 的 Trickle Down 幾乎完全對稱（把找最小變成找最大，並反轉大小於的判斷）。

min-max heap 的刪除操作範例 1：刪除最小值

假設現在有棵樹是先前加入範例操作完的樹：

此時我們要刪除根節點 10，那麼會先把根節點拿掉，換最後一個上去：

目前根節點 20 位於 Min 層，要找到其所有子節點與子孫節點中最小的一個。

子節點：50, 40。
子孫節點：12, 30, 35, 15。

最小的節點是 12（子孫節點）。

由於 12 < 20 因此做交換：

因為 20 降到了子孫節點的位置（Min 層），須確認他有沒有比現在的父節點（Max 層的 50）大。

由於 20 < 50，所以不用換。

最後由於 20 已是葉節點，沒有更下層的子節點了，因此該棵樹已達到 min-max heap 的性質。

min-max heap 的刪除操作範例 2：刪除最大值

接續剛才完成刪除操作的樹：

最大值必定在根節點的子節點中，比較 50 與 40，最大值是 50；移除 50，並將樹的最後一個元素 15 移到原本 50 的位置。

節點 15 目前在 Max 層，要找出它的子孫中最大的一個。

子節點：20, 30。
孫節點：無。

最大的節點是 30（子節點），由於 30 > 15 因此交換。

最後檢查 Max 層的 30 確實大於它的子節點 20 與 15，而 12 依然是全樹最小，最後刪除最大值的操作就完成了，最後的調整也符合 min-max heap 的性質。

deap（Double-Ended Heap）

什麼是 deap？

deap 也是一棵完整二元樹（Complete Binary Tree），用於實作雙端優先佇列（Double-Ended Priority Queue）的資料結構，有一些特別的規則，如下：

根節點為空（Empty Root）：樹的根節點（通常在陣列索引 1）不存放任何有效資料。
左子樹是 Min-Heap：根節點的左子節點（索引 2）是一棵 Min-Heap 的根，因此，整棵樹的最小值必定在索引 2。
右子樹是 Max-Heap：根節點的右子節點（索引 3）是一棵 Max-Heap 的根，因此，整棵樹的最大值必定在索引 3。
對應節點性質（Corresponding Property）：對於左子樹（Min-Heap）上的任何一個節點 $i$ $i$ ，它在右子樹（Max-Heap）上會有一個相同相對位置的對應節點 $j$ $j$ 。
- 規則：節點 $i$ 的值，必須 $\le$ 對應節點 $j$ 的值。
- 如果右邊的對應節點 $j$ 不存在（因為樹還沒長滿），則 $j$ 取那個缺失節點的父節點。

下圖是一個 deap tree：

deap_tree_corrected

以下是各節點間的對應關係：

5 跟 45 對應
10 跟 40
12 跟 30
25 跟 40（對過去 40 底下沒子節點，因此跟空子節點的父節點 40 對應）
20 跟 40（對過去 40 底下沒子節點，因此跟空子節點的父節點 40 對應）
28 跟 30（對過去 30 底下沒子節點，因此跟空子節點的父節點 30 對應）
29 跟 30（對過去 30 底下沒子節點，因此跟空子節點的父節點 30 對應）

deap 的加入操作

將新元素加入 deap 的時間複雜度為 $O(\log n)$ ，操作的核心是先確認新元素該去左邊還是右邊，再做 Bubble Up。

執行步驟：

放置元素：將新元素 $E$ 放在完整二元樹的最後一個位置（維持完整二元樹的形狀）。
尋找對應節點：判斷該新位置是落在 Min-Heap（左側）還是 Max-Heap（右側），並找出它在另一側的對應節點 $C$ 。
比較與交換：
- 如果 $E$ $E$ 落在 Min-Heap（左側）：比較 $E$ $E$ 與對應節點 $C$ $C$ 。
  - 若 $E > C$ ：違反了左 $\le$ 右的規則，將 $E$ 與 $C$ 交換，然後讓 $E$ 在 Max-Heap 中做 Bubble Up Max。
  - 若 $E \le C$ ：沒有違反規則，直接讓 $E$ 在 Min-Heap 中做 Bubble Up Min。
- 如果 $E$ $E$ 落在 Max-Heap（右側）：比較 $E$ $E$ 與對應節點 $C$ $C$ （此時 $C$ $C$ 在左側）。
  - 若 $E < C$ ：違反了左 $\le$ 右的規則，將 $E$ 與 $C$ 交換，然後讓 $E$ 在 Min-Heap 中做 Bubble Up Min。
  - 若 $E \ge C$ ：沒有違反規則，直接讓 $E$ 在 Max-Heap 中做 Bubble Up Max。

deap 的加入操作範例

deap_tree_insertion

假設要在上面這棵樹加入 48 這個元素，一樣加到最後面去：

deap_tree_insertion_2

接著與對應節點比較：

位置 9 在右子樹的對應位置是 13，因為位置 13 不存在，所以找 13 的父節點，也就是位置 6（值為 45）。

規則要求左 $\le$ 右，由於 48 > 45，違反規則，因此將 48 與 45 交換。

deap_tree_insertion_3

再來於目前的樹做 Bubble Up：

現在 48 位於位置 6（Max-Heap），需要檢查它的父節點（位置 3，值為 50）。

由於 48 < 50，符合 Max-heap 的性質，停止加入操作。

deap 的刪除操作

刪除操作分為刪除最小值與刪除最大值，時間複雜度皆為 $O(\log n)$ ，概念是 Trickle Down 後，再進行跨樹驗證。

刪除最小值：最小值永遠在 Min-Heap 的根節點（陣列索引 $2$ $2$ ）。
- 執行步驟：
  1. 取出索引 $2$ 的值（即最小值）。
  2. 將樹的最後一個元素 $L$ 移到索引 $2$ 的位置，並將 Heap 的大小減 1。
  3. 對索引 $2$ 做 Trickle Down Min：在 Min-Heap 中，將 $L$ 不斷與其較小的子節點交換，直到 $L$ 小於其所有子節點，或成為葉節點為止。
  4. 跨樹驗證：當 $L$ $L$ 找到在 Min-Heap 中的最終位置後，它可能違反了左 $\le$ $\leq$ 右的對應規則。
    - 找出 $L$ 在 Max-Heap 中的對應節點 $C$ 。
    - 如果 $L > C$ ，則將 $L$ 與 $C$ 交換，交換後，針對目前在 Max-Heap 上的 $L$ ，做一次 Bubble Up Max，確保 Max-Heap 的性質沒有被破壞。
刪除最大值：最大值永遠在 Max-Heap 的根節點（陣列索引 $3$ $3$ ），如果樹中只有一個元素（在索引 $2$ $2$ ），則直接刪除該元素。
- 執行步驟：
  1. 取出索引 $3$ 的值（即最大值）。
  2. 將樹的最後一個元素 $L$ 移到索引 $3$ 的位置，並將 Heap 的大小減 1。
  3. 對索引 $3$ 執行向下過濾 Trickle Down Max：在 Max-Heap 中，將 $L$ 不斷與其較大的子節點交換，直到 $L$ 大於其所有子節點，或成為葉節點為止。
  4. 跨樹驗證：
    - 當 $L$ 找到在 Max-Heap 中的最終位置後，找出它在 Min-Heap 中的對應節點 $C$ 。
    - 如果 $L < C$ ，則將 $L$ 與 $C$ 交換，交換後，針對目前在 Min-Heap 上的 $L$ ，做一次 Bubble Up Min，確保 Min-Heap 的性質。

deap 的刪除操作範例 1：刪除最小值

繼續用先前加入 48 後的樹當例子：

deap_tree_insertion_3

現在要刪除最小值，而最小值永遠在 Min-Heap 的根節點（位置 2，值為 10），直接拿掉，並將樹的最後一個節點（位置 9，值為 45）移到位置 2。

deap_tree_delete

對位置 2 的 45 做 Trickle Down Min，由於 45 > 15，因此將 45 與 15 交換：

deap_tree_delete_1

此時 45 在位置 4，繼續看子節點，由於 45 > 30，因此將 45 與 30 交換。

deap_tree_delete_2

此時 45 在位置 8，已無子節點，Trickle Down Min 結束。

接著做跨樹驗證：45 現位於 8（Min-Heap），其對應節點是位置 12 的父節點，也就是位置 6（值為 48）。

由於 45 <= 48，沒有違反左 $\le$ 右的規則，不需交換，刪除操作完成。

deap 的刪除操作範例 2：刪除最大值

繼續對剛完成 Delete Min 的這棵樹，執行刪除最大值的操作。

deap_tree_delete_2

最大值永遠在 Max-Heap 的根節點（位置 3，值為 50），直接拿掉，再把樹的最後一個節點（位置 8，值為 45）移到位置 3。

deap_tree_delete_3

對位置 3 的 45 做 Trickle Down Max，比較子節點 48 與 40，48 較大，然後跟 48 做比較：由於 45 < 48，將 45 與 48 交換。

此時 45 在位置 6，已無子節點，Trickle Down Max 結束。

deap_tree_delete_4

跨樹驗證：

45 現在停在位置 6（Max-Heap），其對應的左節點是位置 4（值為 30）。
由於 30 <= 45，沒有違反規則，不需交換，刪除最大值完成。

總整理

堆積（Heap）基礎概念

堆積是一種特殊的完整二元樹（Complete Binary Tree），結構緊湊，適合用一維陣列儲存以提升效率（省去指標），根據節點數值大小，分為兩種：

最大堆（Max-Heap）：父節點 $\ge$ 子節點，根節點為全樹最大值。
最小堆（Min-Heap）：父節點 $\le$ 子節點，根節點為全樹最小值。

調整機制

維持 Heap 性質的兩大操作：

特性	由下而上（Sift-Up / Bubble-Up）	由上而下（Sift-Down / Trickle-Down）
觸發時機	新增資料（Insert）	取出極值（Delete）或陣列原地建構（Heapify）
移動方向	葉節點 $\rightarrow$ 根節點	根節點 $\rightarrow$ 葉節點
比較對象	僅與父節點比較	先找子節點的極大/極小值，再與之比較
時間複雜度	最差 $O(\log n)$	最差 $O(\log n)$

常規 Heap 操作流程（以 Max-Heap 為例）

加入（Insert）：
1. 將新元素放進陣列最尾端。
2. 執行 Sift-Up：不斷與父節點比較，若 $>$ 父節點則互換，直到 $\le$ 父節點或成為根節點。
刪除（Delete Root）：
1. 取出根節點（即最大值）。
2. 將陣列最後一個元素填補至根節點的空缺，並縮減陣列長度。
3. 執行 Sift-Down：不斷與較大的子節點比較，若 $<$ 子節點則互換，直到落至正確位置。

Min-Heap：
性質與操作邏輯與 Max-Heap 完全對稱（找最小、換最小）。
標準建構法（Heapify）：從最後一個非葉節點（索引 $(n/2) - 1$ ）開始，往回對每個節點執行 Sift-Down，時間複雜度只需 $O(n)$ 。

Min-Max Heap（雙端優先佇列）

結合兩種 Heap 的特性，能以 $O(1)$ 的時間找到最大與最小值。

層級交替：
- Min 層（偶數深度，如 Root）：節點必為子樹中最小，全樹最小值在 $A[1]$ 。
- Max 層（奇數深度）：節點必為子樹中最大，全樹最大值在 $A[2]$ 或 $A[3]$ 。

Min-Max Heap 操作

加入（Bubble Up）：
1. 放陣列尾端，檢查父節點是否違反當前層級規則。
2. 若違反，與父節點交換，並往上執行另一個層級的 Bubble Up（例如：違反 Min 層規則，換位後執行 Bubble Up Max）。
3. 若無違反，直接在當前層級的祖先中執行 Bubble Up。
刪除極值（Trickle Down）：
1. 取出 Root（Min）或子節點最大者（Max）。
2. 用最後一個元素遞補。
3. 執行 Trickle Down：在子節點與子孫節點中尋找極值交換，若與子孫交換，需再額外檢查是否違反夾在中間的父節點規則（Min/Max層交替特性）。

Deap (Double-Ended Heap)

同樣用於雙端優先佇列，但結構拆分為左右兩半：

根節點為空： $A[1]$ 不放資料。
左子樹（Min-Heap）：最小值在 $A[2]$ 。
右子樹（Max-Heap）：最大值在 $A[3]$ 。
對應性質：左子樹節點 $i \le$ 右子樹對應節點 $j$ （若 $j$ 不存在，則對應其父節點）。

Deap 操作

加入：
1. 放陣列尾端。
2. 跨樹比較：找出另一側的對應節點。
3. 若違反左 $\le$ 右規則，則互換，並在換過去的那一側執行 Bubble Up；若無違反，直接在當前側執行 Bubble Up。
刪除極值：
1. 取出 $A[2]$ （Min）或 $A[3]$ （Max），並用最後一個元素遞補。
2. 對遞補的元素在自己的樹中執行 Trickle Down。
3. 跨樹驗證：到底後，找出另一側的對應節點比較，若違反左 $\le$ 右，則兩者互換，並對換過去的新位置執行一次 Bubble Up 確保性質。