原住民族考試四等考試-電子工程類科計算機概要105 年第 17 題單選題

一最小堆積（min-heap）儲存有 $n$ 個關鍵值（keys），其取出最小關鍵值（extract-min）及插入（insert）一個關鍵值之最差時間複雜度分別為何？

Aextract-min：

Θ (1)

，insert：

Θ (n)

Bextract-min：

Θ (1)

，insert：

Θ (lo g n)

Cextract-min：

Θ (lo g n)

，insert：

Θ (lo g n)

正確答案

Dextract-min：

Θ (lo g n)

，insert：

Θ (n)

答案與詳解

正確答案

Min-Heap 的 Extract-Min（取出並重整）與 Insert（插入並重整）皆需沿著樹高進行調整，最差時間複雜度皆為 Θ(log n)。

正確。Extract-Min 需將最後節點移至根部並向下重整 (Heapify-down)；Insert 需將新節點放至尾部並向上重整 (Heapify-up)。兩者最差情況皆需走過樹的高度，時間複雜度為 Θ(log n)。

考點：Find-Min考點：Extract-Min考點：Heap 操作複雜度考點：Insert

載入中…

Examly 收錄 38 萬+ 道歷屆題目，每題都有像這樣的精選詳解。免費下載，立即開練。

一最小堆積（min-heap）儲存有n個關鍵值（keys），其取出最小關鍵值（extract-min）及插入（insert）一個關鍵值之最差時間複雜度分別為何？