地特四等
112年
[電子工程] 計算機概要
第 14 題
堆積（Heap）經常使用陣列來儲存。將 70 插入下圖所示陣列代表的最大堆積後，70 所在位置的索引值為何？
- A 11
- B 5
- C 2
- D 1
思路引導 VIP
若要維持「父節點永遠大於子節點」的規則，當我們把新成員 70 擺在陣列最後一個空位時，它該如何尋找自己的「直系長輩」進行實力比對？而這些長輩在陣列編號上的數學規律又是什麼呢？
🤖
AI 詳解
AI 專屬家教
恭喜你準確地掌握了最大堆積（Max Heap）的動態調整邏輯！這類題目考驗的是你對二元樹（Binary Tree）在陣列中存儲特性的理解。當我們將 70 插入現有的堆積時，必須維持其結構完整性：首先將新元素放在陣列的最末端，即索引 11 的位置，隨後執行向上調整（Up-Heap）程序。 在最大堆積中，任何節點的值都必須大於或等於其子節點。根據陣列索引規律，索引 $i$ 的父節點位於 $\lfloor i/2 \rfloor$。首先，70 會與索引 5 的父節點（38）比較，因 $70 > 38$ 而進行交換；接著，位於索引 5 的 70 會再與索引 2 的父節點（60）比較，同樣因 $70 > 60$ 再次交換。最後，70 來到索引 2 並與根節點（索引 1 的 88）比較，此時 $70 < 88$，調整便在索引 2 告一段落。這題的難度切入點在於考生是否能細心地完成兩次連續的交換，並精確計算出父節點的索引值，是一道非常經典且具鑑別度的基礎資料結構試題。