[理工] LeftistHeap能不能DecreaseKey(資料結構)

看板Grad-ProbAsk作者 (熱火三)時間8年前 (2017/06/11 21:12), 8年前編輯推噓3(3推 0噓 8→)
留言11則, 4人參與, 最新討論串1/1
我查詢leftist heap,網路上有資料說它不支援decrease key的指令 但我不懂的是不能把它當作一般binary heap操作嗎 像一般binary heap的話，decrease key複雜度就是O(lgn) 但是leftist heap是因為什麼原因不能像那樣操做呢 感謝各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.171.169.169 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1497186737.A.2BD.html
→
06/11 21:40, , 1F
因為一般Binary heap有Complete性質吧？
06/11 21:40, 1F
→
06/11 22:17, , 2F
樓上正解，leftist heap 實作通常會用 linked list
06/11 22:17, 2F
→
06/11 23:01, , 3F
沒有complete性質就不能decrease key嗎？
06/11 23:01, 3F
假如處理一個min heap,我先選了一個點，然後把他的key減少， 再比較看看他的key有沒有比他的父母高，如果沒有兩者就交換 這樣一路比較完不是就完成decreasekey了？ ※ 編輯: heatthree (1.171.169.169), 06/11/2017 23:05:03
推
06/12 06:54, , 4F
應該是可以 decreasekey 只是速度不快
06/12 06:54, 4F
→
06/12 10:30, , 5F
重點是複雜度吧 @@
06/12 10:30, 5F
→
06/12 10:30, , 6F
妳還要維持 leftist heap 的性質
06/12 10:30, 6F
比如說下面有一個 leftist heap 1 3 2 4 5 假如我把5 decrease為0 ,然後0<->3 , 0<->1 ,這樣感覺就完成decreasekey了 0 1 2 4 3 而且leftist heap性質維持，因為整個heap的架構沒變,而且複雜度也只有O(lgn) 請問我有哪裡想錯的嗎，感謝。 ※ 編輯: heatthree (1.171.42.166), 06/12/2017 12:27:11
→
06/12 14:58, , 7F
可以的，那妳要先確保 linked list 是雙向的
06/12 14:58, 7F
→
06/12 14:59, , 8F
教科書上的 node 是往下儲存的，實作上妳要記得改
06/12 14:59, 8F
→
06/12 16:39, , 9F
感謝回答
06/12 16:39, 9F
推
06/12 21:25, , 10F
Leftist 的高度有保證是 O(lg n) 嗎？
06/12 21:25, 10F
推
06/13 02:38, , 11F
沒有吧
06/13 02:38, 11F
‣ 更多 heatthree 的文章
文章代碼(AID): #1PFK6nAz (Grad-ProbAsk)