在一個有 $n$ 個數字、以陣列實作的最大二元堆積（Max Binary Heap）中，要尋找最大值及第二大值，其最差時間複雜度（worst case time complexity）分別為何？

A最大值：

Θ (1)

，第二大值：

Θ (1)

正確答案

B最大值：

Θ (1)

，第二大值：

Θ (lo g n)

C最大值：

Θ (1)

，第二大值：

Θ (n)

D最大值：

Θ (lo g n)

，第二大值：

Θ (lo g n)

答案與詳解

正確答案

Max-Heap 根節點即最大值,第二大必為根的兩子之一,皆 Θ(1)。

正確。最大值 = 根 → Θ(1);第二大值必為根的左/右子之一,比較一次 → Θ(1)。

載入中…

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

在一個有 n 個數字、以陣列實作的最大二元堆積（Max Binary Heap）中，要尋找最大值及第二大值，其最差時間複雜度（worst case time complexity）分別為何？