[理工] 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

没有吧

继续阅读