調查局三等申論題
111年
[電子科學組] 計算機概論
第 三 題
最大堆積（Max Heap）是一個完整二元樹（complete binary tree），將以下數列 12,15,13,26 依序插入最大堆積中，其時間複雜度為何？（20 分）
（題目附有現存最大堆積結構圖，根節點為10，其下為8, 3，8之下為5, 2，3之下為1）
（題目附有現存最大堆積結構圖，根節點為10，其下為8, 3，8之下為5, 2，3之下為1）
📝 此題為申論題
思路引導 VIP
看到 Max Heap 插入題，首要聯想「維持完整二元樹結構（插尾端）」與「Bubble-up 向上調整（與父節點比較交換）」兩大核心步驟，時間複雜度則直接對應樹的高度 $O(\log n)$。解題時強烈建議將樹結構轉為 1-based 的一維陣列，利用父節點索引公式 $\lfloor i/2 \rfloor$ 進行逐層推演，既能展現資料結構的底層實作，也能避免手繪圖容易產生的失誤。
🤖
AI 詳解
AI 專屬家教
【解題思路】利用 Max Heap（最大堆積）的「向上調整（Bubble-up）」演算法，將新元素置於完整二元樹最尾端，再藉由陣列索引公式逐步與父節點比較與交換，最後分析其比較次數與樹高的關係推導時間複雜度。 【詳解】 壹、理論定義與時間複雜度
▼ 還有更多解析內容
最大堆積插入與複雜度
💡 最大堆積插入需維持完整二元樹屬性，透過向上調整確保父大於子。
🔗 Max Heap 插入運算流程
- 1 置於末端 — 將新元素放入完整二元樹最後一個位置。
- 2 向上比較 — 將新元素與其父節點 (索引 i/2) 進行比較。
- 3 執行互換 — 若新元素值大於父節點則互換，否則停止。
- 4 完成堆積 — 重複直到到達根節點或滿足最大堆積屬性。
↓
↓
↓
🔄 延伸學習：延伸學習：刪除根節點後需將末端遞補至根部，改執行「向下調整」。
