[理工] [DS] Heap
作者: k3331863 (Jay) 2015-01-27 23:54:05
想請問以下兩題heap相關的題目
1.
![]()
?1
出自MIT 線上課程(
![]()
)
答案:False
;solution:
![]()
?1
和朋友的結論是 他是問search不是extract-min or insert
所以與heapify無關
2.
![]()
?1
出自政大資科98年
答案:B
; 算是很平常的heap考法
; 假設是min-heap
; extract-min一次後選root
; O(logn)
但是偏偏剛好聯想到第一題
題目問[worst case] [find second min] 且沒講max or min heap
就給他選了O(n)
不知道版上各位的看法如何
有時候覺得自己想太多
1.
?1出自MIT 線上課程(
)答案:False
;solution:
?1和朋友的結論是 他是問search不是extract-min or insert
所以與heapify無關
2.
?1出自政大資科98年
答案:B
; 算是很平常的heap考法
; 假設是min-heap
; extract-min一次後選root
; O(logn)
但是偏偏剛好聯想到第一題
題目問[worst case] [find second min] 且沒講max or min heap
就給他選了O(n)
不知道版上各位的看法如何
有時候覺得自己想太多
作者: galapous (墨) 2015-01-28 00:06:00
我覺得第一題不是問第二大的所以才是O(n)講錯 第二小第一題應該是說對任意元素x假設他是k-th大 那要找k+1-th
作者: GuardmanMart (Mart) 2015-01-28 00:14:00
感覺兩題要問的東西不一樣!? 第一題是找出某key值x以下最大的key值，這個用刪除最小點的方法應該沒辦法得到；第二題就純粹是問整棵heap第二小的點了
作者: galapous (墨) 2015-01-28 00:15:00
同樓上看法,不過第二題沒講min-heap我看到會抖
作者: FRAXIS (喔喔) 2015-01-28 00:55:00
min-heap中找第k小的元素是可以在O(k lg k)時間內找到的..
作者: galapous (墨) 2015-01-28 08:28:00
O(klgk)平均起來會比O(n)大吧@@
作者: qoozxc789 (呵呵) 2015-01-28 08:53:00
第k小跟第二小不一樣吧?
作者: zhwang2123 (123456) 2015-01-28 12:35:00
第二大 = 第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.