地方政府公務人員四等-資訊處理類科計算機概要108 年第 26 題單選題
若使用陣列實作最大堆積（max-heap），下列敘述何者錯誤？
A尋找一個節點的子節點的時間複雜度為 O(1)
B尋找一個節點的父節點的時間複雜度為 O(1)
C節點的分支度（degree）為 0 或 2正確答案
D新增一個數值至一個具有 n 個節點的最大堆積的時間複雜度為 $O(\log n)$
C正確答案
最大堆積是完全二元樹，節點分支度可能為 0、1 或 2，不是只有 0 或 2。
為什麼答案是 C
此為本題要選的錯誤敘述。堆積是完全二元樹（complete binary tree），倒數第二層最右側的內部節點可能只有左子節點，即分支度為 1。分支度只有 0 或 2 是「完滿二元樹 full binary tree」的性質，兩者觀念混淆。
載入中…
完整詳解
Pro · 無限重點 最大堆積是完全二元樹，節點分支度可能為 0、1 或 2，不是只有 0 或 2。
完全二元樹最後一個有子節點的父節點，可能只有左子節點（分支度=1），故 C 錯。
逐選項分析
A✕
陣列實作堆積時，索引 i 的左子為 2i、右子為 2i+1（或 2i+1、2i+2），直接計算即可，時間複雜度 O(1)。
B✕
索引 i 的父節點為 ⌊i/2⌋（或 ⌊(i-1)/2⌋），一次除法即可定位，時間複雜度 O(1)。
C✓ 正確
此為本題要選的錯誤敘述。堆積是完全二元樹（complete binary tree），倒數第二層最右側的內部節點可能只有左子節點，即分支度為 1。分支度只有 0 或 2 是「完滿二元樹 full binary tree」的性質，兩者觀念混淆。
D✕
新增時將元素放至陣列末端，再向上調整（sift-up）至多走樹高度 log n 層，故時間複雜度為 O(log n)。
陣列實作 Max-Heap 操作複雜度
| 操作 | 方法 | 時間複雜度 |
|---|
| 找子節點 | index 2i、2i+1 | O(1) |
| 找父節點 | index ⌊i/2⌋ | O(1) |
| 插入 Insert | 放末端 + sift-up | O(log n) |
| 刪除最大 Delete-Max | 取根 + sift-down | O(log n) |
| 建堆 Build-Heap | 由下而上 heapify | O(n) |
C 選項把「完滿二元樹 (Full Binary Tree)」的性質套到「完全二元樹 (Complete Binary Tree)」上。Heap 是完全二元樹，最後一個內部節點可能只有左子，因此會出現分支度為 1 的節點。這是資料結構考題最愛的中英文術語陷阱。 
