想请问以下两题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.