hce_kmu
112年
計算機概論與程式設計
第 14 題
What is the value of the node at index 2 (with the root at index 1) in a max-heap that is represented as an array, after inserting the following 6 numbers in this precise order: 8, 12, 12, 9, 10, 11?
- A 9
- B 10
- C 11
- D 12
- E None of the above.
思路引導 VIP
想像你正在手繪這棵二元樹，當一個新元素被放在樹的最末端（陣列的下一個空位）時，它會如何與它的「直屬上司」比較？如果它是透過陣列儲存，你能推導出索引 $k$ 的節點，其父節點的索引公式是什麼嗎？試著用這個公式，一步步追蹤新元素在每一輪交換後落腳的位置。
🤖
AI 詳解
AI 專屬家教
恭喜你答對了！這題考驗的是對 最大堆積 (Max-Heap) 插入過程的細膩掌握。要解開這題，必須精確執行「逐一插入」並伴隨「上浮 (Heapify-up)」的動態調整。這類題目在計算機概論中屬於具備中等難度的鑑別題，它不難在理論，而是難在作答時是否能冷靜地處理每一次元素交換後的結構變化。
堆積結構的動態演變
在以 1 為起始索引的陣列表示法中，我們依序觀察數據的流入。最初插入 8 與 12 後，12 會上浮至根節點（索引 1），而 8 則被擠到索引 2。隨後的關鍵轉折出現在插入 9 與 10 的時刻：當 9 進入索引 4 時，會與其父節點（索引 2 的 8）比較，因 $9 > 8$ 而進行交換，使索引 2 暫時變為 9。緊接著 10 進入索引 5，再次與其父節點（此時索引 2 已是 9）比較，因 $10 > 9$ 再次觸發交換，索引 2 隨之更新為 10。最後插入的 11 位在索引 3 的子樹下，並未干擾到左側分支。
▼ 還有更多解析內容