假設一個堆積( H e a p ) 共有n 個元素,在最壞的情形下,下列之描述何者是錯誤的?

題目

假設一個堆積( H e a p ) 共有n 個元素,在最壞的情形下,下列之描述何者是錯誤的?

1. (1) 插入一個元素到H e a p ,其時間複雜度為θ ( l o g n )
2. (2) 從M a x H e a p 找最大值,其時間複雜度為 θ ( l o g n )
3. (3) 從M i n H e a p 刪除最小值,其時間複雜度為θ ( l o g n )
4. (4) 從M a x H e a p 找最小值,其時間複雜度為θ ( n )

官方答案

(2) 從M a x H e a p 找最大值,其時間複雜度為 θ ( l o g n )

解析

Max Heap 的最大值必定位於根節點，直接讀取根即可取得，時間複雜度為 θ(1)，因此第 2 項敘述錯誤。插入元素要放到陣列末端再向上調整，調整高度為 log n，故為 θ(log n)；從 Min Heap 刪除最小值是取出根後把末元素移到根再向下調整，同樣為 θ(log n)；在 Max Heap 中找最小值必須檢查沒有子節點的葉節點，最壞需掃描約 n/2 個節點，為 θ(n)。故選 2。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF