[理工] [DS] Heap
想請問以下兩題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)
不知道版上各位的看法如何
有時候覺得自己想太多
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.154.218
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422374048.A.5D4.html
※ 編輯: k3331863 (114.24.154.218), 01/28/2015 00:01:29
※ 編輯: k3331863 (114.24.154.218), 01/28/2015 00:03:08
推
01/28 00:06, , 1F
01/28 00:06, 1F
→
01/28 00:06, , 2F
01/28 00:06, 2F
→
01/28 00:08, , 3F
01/28 00:08, 3F
推
01/28 00:14, , 4F
01/28 00:14, 4F
→
01/28 00:14, , 5F
01/28 00:14, 5F
→
01/28 00:14, , 6F
01/28 00:14, 6F
推
01/28 00:15, , 7F
01/28 00:15, 7F
推
01/28 00:55, , 8F
01/28 00:55, 8F
→
01/28 08:28, , 9F
01/28 08:28, 9F
推
01/28 08:53, , 10F
01/28 08:53, 10F
→
01/28 12:35, , 11F
01/28 12:35, 11F
→
01/28 13:06, , 12F
01/28 13:06, 12F
→
01/28 13:06, , 13F
01/28 13:06, 13F
→
01/28 13:06, , 14F
01/28 13:06, 14F
→
01/28 13:12, , 15F
01/28 13:12, 15F
→
01/28 13:12, , 16F
01/28 13:12, 16F
→
01/28 13:12, , 17F
01/28 13:12, 17F
→
01/28 13:16, , 18F
01/28 13:16, 18F
※ 編輯: k3331863 (114.24.180.185), 01/28/2015 13:21:15
推
01/28 23:18, , 19F
01/28 23:18, 19F