問題詳情
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