想請問以下兩題heap相關的題目
1.
http://i.imgur.com/jBYgIRv.png?1
出自MIT 線上課程(http://ppt.cc/mMg2)
答案:False
;solution:http://i.imgur.com/ySIzOmT.png?1
和朋友的結論是 他是問search不是extract-min or insert
所以與heapify無關
2.
http://i.imgur.com/BeNYJnz.png?1
出自政大資科98年
答案:B
; 算是很平常的heap考法
; 假設是min-heap
; extract-min一次後選root
; O(logn)
但是偏偏剛好聯想到第一題
題目問[worst case] [find second min] 且沒講max or min heap
就給他選了O(n)
不知道版上各位的看法如何
有時候覺得自己想太多
我覺得第一題不是問第二大的所以才是O(n)講錯 第二小第一題應該是說對任意元素x假設他是k-th大 那要找k+1-th
感覺兩題要問的東西不一樣!? 第一題是找出某key值x以下最大的key值，這個用刪除最小點的方法應該沒辦法得到；第二題就純粹是問整棵heap第二小的點了
同樓上看法,不過第二題沒講min-heap我看到會抖
作者:
FRAXIS (喔喔)
2015-01-28 00:55:00min-heap中找第k小的元素是可以在O(k lg k)時間內找到的..
第二大 = 第n-1小 要找O(nlogn) 還不如用循序O(n)
作者: k3331863 (Jay) 2015-01-28 13:06:00
只能說第二題出得太爛了 比較令人在意的點是 遇到題目問heap的search or find 和 extract-min or max 的worstcase 還有第一題的any 和第二題的second之前寫完第一題後的認知是 在heap內search是需要O(n)的相較之下 第二題 要extract-min. second 和 first 不都是O(log) 想考heapify又講得這麼不明不白更正O(logn)
作者:
FRAXIS (喔喔)
2015-01-28 23:18:00第二題 min-heap裡面找第二小是O(1).. 如果不extract.