問題詳情

17 一最小堆積（min-heap）儲存有 n 個關鍵值（keys），其取出最小關鍵值（extract-min）及插入（insert）一個關鍵值之最差時間複雜度分別為何？
(A)extract-min：Θ（1），insert：Θ（n）
(B)extract-min：Θ（1），insert：Θ（log n）
(C)extract-min：Θ（log n），insert：Θ（log n）
(D)extract-min：Θ（log n），insert：Θ（n）

參考答案

答案：C
難度：困難0.351171
統計：A(44),B(80),C(105),D(24),E(0)

用户評論

【2587410】評論

最差時間複雜度分別為extract-min：Θ（log n），insert：Θ（log n）

【人人都可以是食神!!!】評論

1.重點：min-heap　←　已經是一個二元樹了，樹根是最小的值。2.不論取最小或新增一個，最差時間複雜度 都是 log(n) <= 底是２，不是10。參考來源：http://notepad.yehyeh.net/Content/Algorithm/Sort/Heap/Heap.phphttps://yotsuba1022.gitbooks.io/data-structure-note/content/heap-tree.html