Q25.
假設一個堆積(Heap)共有n 個元素，在最壞的情形下，下列之描述何者是錯誤的？
電腦軟體設計共同科目 · 乙級 · Q25
難易度分析
3 / 5
本題要求考生精確區分堆積結構中不同操作的時間複雜度，包含常數時間、對數時間與線性時間的比較，且需辨識搜尋極值與維護結構操作之間的差異，具有一定的概念辨析度。
正確答案：②從Max Heap 找最大值，其時間複雜度為θ(log n)
② 從Max Heap 找最大值，其時間複雜度為θ(log n):Max Heap 的最大值 必定位於 根節點，無需進行任何調整或搜尋，直接回傳即可，時間複雜度為 θ(1) 而非 θ(log n)，故此描述錯誤。
錯誤選項解析
- ① 插入一個元素到Heap，其時間複雜度為θ(log n):插入元素至 Heap 時，需執行 Heapify-Up（上溯調整），由新節點沿路徑向上比較並交換，最壞情況為樹高，故時間複雜度為 θ(log n)，此描述正確。
- ③ 從Min Heap 刪除最小值，其時間複雜度為θ(log n):Min Heap 刪除最小值 即刪除根節點，需將最後一個元素移至根後執行 Heapify-Down（下溯調整），最壞情況為樹高，故時間複雜度為 θ(log n)，此描述正確。
- ④ 從Max Heap 找最小值，其時間複雜度為θ(n):Max Heap 的最小值 可能出現在任一 葉節點，無法利用 Heap 特性快速定位，必須遍歷所有葉節點，故時間複雜度為 θ(n)，此描述正確。
Learning Tip
"此題核心考點在於區分 Heap 的極值存取特性 與 操作複雜度。Max Heap 根節點即最大值、Min Heap 根節點即最小值，兩者皆為 θ(1) 直接存取；而插入與刪除操作均需執行 Heapify 調整，複雜度為 θ(log n)。常見陷阱是混淆「搜尋極值」與「刪除極值」的差異：刪除需維持 Heap 結構故為 θ(log n)，但直接讀取根節點僅需 θ(1)。另外，尋找 Heap 中的「非根極值」因缺乏排序保證，必須線性搜尋 θ(n)。"
學員答題分佈
①插入一個元素到Heap，其時間複雜度為θ(log n)0%
②從Max Heap 找最大值，其時間複雜度為θ(log n)0%
③從Min Heap 刪除最小值，其時間複雜度為θ(log n)0%
④從Max Heap 找最小值，其時間複雜度為θ(n)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！