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

[heatthree (熱火三)]

我查詢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
→ sarsman: 因為一般Binary heap有Complete性質吧？
→ kyuudonut: 樓上正解，leftist heap 實作通常會用 linked list
→ heatthree: 沒有complete性質就不能decrease key嗎？
   假如處理一個min heap,我先選了一個點，然後把他的key減少，
   再比較看看他的key有沒有比他的父母高，如果沒有兩者就交換
   這樣一路比較完不是就完成decreasekey了？
※ 編輯: heatthree (1.171.169.169), 06/11/2017 23:05:03
推 FRAXIS: 應該是可以 decreasekey 只是速度不快
→ kyuudonut: 重點是複雜度吧 @@
→ kyuudonut: 妳還要維持 leftist heap 的性質
  比如說下面有一個 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
→ kyuudonut: 可以的，那妳要先確保 linked list 是雙向的
→ kyuudonut: 教科書上的 node 是往下儲存的，實作上妳要記得改
→ heatthree: 感謝回答
推 FRAXIS: Leftist 的高度有保證是 O(lg n) 嗎？
推 sarsman: 沒有吧