若使用陣列實作最大堆積（max-heap），下列敘述何者錯誤？
A尋找一個節點的子節點的時間複雜度為 O(1)
B尋找一個節點的父節點的時間複雜度為 O(1)
C節點的分支度（degree）為 0 或 2正確答案
D新增一個數值至一個具有 n 個節點的最大堆積的時間複雜度為 O(log n)
答案與詳解
為什麼答案是 C
此為本題要選的錯誤敘述。堆積是完全二元樹（complete binary tree），倒數第二層最右側的內部節點可能只有左子節點，即分支度為 1。分支度只有 0 或 2 是「完滿二元樹 full binary tree」的性質，兩者觀念混淆。
考點：陣列索引計算考點：父節點索引考點：完全 vs 完滿二元樹考點：插入 sift-up
載入中…
