作者q5332159 (chiu)
看板Grad-ProbAsk
标题[理工] 资结 Fibonacci heap delete x
时间Wed Oct 31 15:46:00 2018
http://i.imgur.com/1LC1I8a.jpg
关於delete x的时间
查了一下之後的理解是
因为要先decrease到最小再delete-min
所以是O(log n) (delete-min时merge的时间)
但是笔记下方又写如果不是min的话采lazy merge
这样为什麽还需要O(log n)呢?
谢谢各位～
-----
Sent from JPTT on my HTC_D830x.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.8.34.253
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1540971962.A.757.html
1F：推 alan23273850: 所以按照你的说法，取两个case比较久的那个，就还 10/31 16:50
2F：→ alan23273850: 是O(lgn)阿，这是复杂度定义 10/31 16:50
3F：→ q5332159: 了解～还有一个问题就是delete x到底需不需要merge到不 10/31 21:43
4F：→ q5332159: 同高度 还是lazy就好？因为查到的是不管是删最小或任意 10/31 21:43
5F：→ q5332159: 数都还是会做到delete-min 这个动作 那不就不lazy了吗 10/31 21:43