[理工] LeftistHeap能不能DecreaseKey(資料結構) heatthree PTT批踢踢實業坊

作者: heatthree (熱火三) 2017-06-11 21:12:14

我查詢leftist heap,網路上有資料說它不支援decrease key的指令
但我不懂的是不能把它當作一般binary heap操作嗎
像一般binary heap的話，decrease key複雜度就是O(lgn)
但是leftist heap是因為什麼原因不能像那樣操做呢
感謝各位

作者: sarsman (DeNT15T♠) 2017-06-11 21:40:00

因為一般Binary heap有Complete性質吧？

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2017-06-11 22:17:00

樓上正解，leftist heap 實作通常會用 linked list

作者: heatthree (熱火三) 2017-06-11 23:01:00

沒有complete性質就不能decrease key嗎？

作者: FRAXIS (喔喔) 2017-06-12 06:54:00

應該是可以 decreasekey 只是速度不快

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2017-06-12 10:30:00

重點是複雜度吧 @@妳還要維持 leftist heap 的性質可以的，那妳要先確保 linked list 是雙向的教科書上的 node 是往下儲存的，實作上妳要記得改

作者: heatthree (熱火三) 2017-06-12 16:39:00

感謝回答

作者: FRAXIS (喔喔) 2017-06-12 21:25:00

Leftist 的高度有保證是 O(lg n) 嗎？

作者: sarsman (DeNT15T♠) 2017-06-13 02:38:00

沒有吧

繼續閱讀