普考-資訊處理計算機概要108 年第 26 題單選題

若使用陣列實作堆積（heap），將一個具有 $n$ 個元素的陣列建立成最大堆積（max-heap）的時間複雜度，最佳為下列何者？

θ (lo g n)

θ (n)

正確答案

θ (n lo g n)

θ (n^{2})

答案與詳解

正確答案

使用 bottom-up（Floyd's build-heap）建堆,時間複雜度為 Θ(n)。

正確。Floyd 的 bottom-up 建堆法可在 Θ(n) 內完成。

載入中…

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

若使用陣列實作堆積（heap），將一個具有 n 個元素的陣列建立成最大堆積（max-heap）的時間複雜度，最佳為下列何者？