[理工] [資結] Heap

看板Grad-ProbAsk作者 (jim)時間14年前 (2011/09/08 01:15), 編輯推噓7(7推 0噓 5→)
留言12則, 6人參與, 最新討論串1/1
True or False: Searching for a key in a heap takes worst-case time O(n) True.... 為什麼是O(n)?? 有大大可以解釋一下嗎?? 我看search都是O(1)..... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 223.141.91.82
推
09/08 08:02, , 1F
search應該只要O(logn)吧?! 就tree height
09/08 08:02, 1F
推
09/08 08:08, , 2F
heap存的時候又不像binary search tree一樣很有次序..
09/08 08:08, 2F
推
09/08 13:50, , 3F
贊同樓上
09/08 13:50, 3F
推
09/08 20:14, , 4F
Search是O(n)..
09/08 20:14, 4F
→
09/08 20:47, , 5F
那是如何算出O(n)?..是以建立Heap來算的嗎?
09/08 20:47, 5F
推
09/08 21:18, , 6F
找最大或最小才是O(1)吧 他指說找一個key可能是heap中的任
09/08 21:18, 6F
→
09/08 21:20, , 7F
何值 所以最糟就是traverse 整個n個元素的heap了才找到
09/08 21:20, 7F
→
09/08 21:22, , 8F
就如同F大說的heap只有最大最小放在最上面 其他都是散亂的
09/08 21:22, 8F
→
09/08 22:27, , 9F
樓上講解的真是詳細...太感謝你了!!
09/08 22:27, 9F
推
09/13 13:13, , 10F
if heap is skewed , it takes O(n) time
09/13 13:13, 10F
推
09/14 22:10, , 11F
如果是一般的min-heap 應該是不可能skew的..
09/14 22:10, 11F
→
09/11 14:30, , 12F
就如同F大說的heap https://daxiv.com
09/11 14:30, 12F
‣ 更多 jim055006 的文章
文章代碼(AID): #1EPwQyXU (Grad-ProbAsk)