對稱最小最大堆積 (Symmetric Min-Max Heap，SMMH)

Def

為 Complete Binary Tree，支援雙端優先佇列（double-ended priority queue）的實作。 Insert、delete-min、delete-max 操作皆為 $O(\log n)$ 時間複雜度。需滿足以下性質：

Root 不存在任何資料。
左兄弟 ≤ 右兄弟資料（left sibling <= right sibling data）【性質 P₁】
若節點 X 有祖父節點，則「祖父的左子點 ≤ X」【性質 P₂】（Min heap 性質）
若節點 X 有祖父節點，則「祖父的右子點 ≥ X」【性質 P₃】（Max heap 性質）

對等於：假設 elements(N) ≠ 0，則 N 滿足以下性質：

Q1：N 的左子點具有 elements(N) 中的最小值。
Q2：若 N 有右子點，則其右子點具有 elements(N) 中的最大值。
📝 註解：
- X 若有對等節點（兄弟），則最小值必為 X 左子樹中某個節點，
- 最大值必為 X 右子樹中某個節點。

INSERT X IN SMMH

X 置於最後一個節點之下一個位置
Repeat 檢查與調整：
1. Check P1 (先確保同層左右節點滿足以下規定)：
  - 判斷是否滿足左兄弟 <= 右兄弟。
  - 若違反，則執行 SWAP（交換左右 sibling）。
2. Check P2 / P3 (再檢查 P2/P3 的祖父性質)：
  - P2：祖父的左子點 <= X（min heap 性質）
  - P3：祖父的右子點 >= X（max heap 性質）
  - 如果違反其中之一，則 斜上或向上調整（與祖父交換）
直到 P1、P2、P3 皆滿足為止

範例：插入值 X = 2

原始節點順序（Level-order）：
root, 4, 80, 8, 60, 6, 40, 12, 20, 10, 16, 14, 30

即：_, 4, 80, 8, 60, 6, 40, 12, 20, 10, 16, 14, 30

插入 2 前：

              (root)
              /     \
            4         80
          /   \     /   \
         8    60   6     40
       /  \  /  \  / \
     12  20 10 16 14 30

插入節點 2 至下一個空位：

              (root)
              /     \
            4         80
          /   \     /   \
         8    60   6     40
       /  \  /  \  / \   /
     12  20 10 16 14 30  2

2 的祖父是 80，且 6 > 2，違反 P2 → 與 6 交換 (往斜上方)：

              (root)
              /     \
            4         80
          /   \     /   \
         8    60   2     40
       /  \  /  \  / \   /
     12  20 10 16 14 30  6

2 現在在 index 4，其祖父是 4，且 4 > 2，違反 P2 → 與 4 交換 (往斜上方)：

✅ 最終結果：

              (root)
              /     \
            2         80
          /   \     /   \
         8    60    4     40
       /  \  /  \  / \   /
     12  20 10 16 14 30  6

DELETE-MIN in SMMH

刪除最小值一定從 左子樹的 root 開始（因為整棵樹的 min 就在這裡），並形成一個空格（E）。
將 最後一個節點 X 移至空格 E 的位置，暫時放置。
接著開始從 E 開始，依照 SMMH 的 P1（左右兄弟順序）與 P2（祖父左子 <= 自己）進行調整：
- 若違反 P1，則與兄弟節點交換。
- 若違反 P2，則向下與「較小的孫子節點」交換。
P3 無需檢查，因為刪除的是 min，不會影響 max heap 區域。

🧠 重點心得： 就是去找兄弟的左子點和自己的左子點比大小，小的繼任這個空格直到 P1 和 P2 都對。

DELETE-MIN in SMMH 範例流程

以下是從 SMMH 中刪除最小值的完整範例（以圖示方式說明）：

🔹 初始狀態

              (root)
              /     \
            2         80
          /   \     /   \
         8    60    4     50
       /  \  /  \  / \   / \
     12  20 10 16 14 30  6  40

🔹 Step 1：刪除最小值 `2`，形成空格 E，並將最後節點 `40` 移上來

              (root)
              /     \
            E         80
          /   \     /   \
         8    60    4     50
       /  \  /  \  / \   / \
     12  20 10 16 14 30  6 40 (last node X)

🔹 Step 2：將 `40` 放入空格 E 的位置

              (root)
              /     \
           (40)       80
          /   \     /   \
         8    60    4     50
       /  \  /  \  / \   / 
     12  20 10 16 14 30  6

🔹 Step 3：檢查 `40` 是否違反 P1/P2

最小的孫子為 4
與 4 交換（斜下）

              (root)
              /     \
            4         80
          /   \     /   \
         8    60  (40)    50
       /  \  /  \  / \    / 
     12  20 10 16 14 30  6

🔹 Step 4：繼續往下檢查 `40`

最小的孫子為 30
與 30 交換

              (root)
              /     \
            4         80
          /   \     /   \
         8    60    6     50
       /  \  /  \  / \    /
     12  20 10 16 14 30 (40)

✅ 最終完成調整。

每次都與「最小的孫子」進行交換，直到符合 P1、P2。

Def