蒟蒻求助左偏树
  • 板块学术版
  • 楼主_jhq
  • 当前回复13
  • 已保存回复13
  • 发布时间2021/5/18 21:59
  • 上次更新2023/11/4 23:05:36
查看原帖
蒟蒻求助左偏树
178910
_jhq楼主2021/5/18 21:59

RT。

左偏树删除任意节点时(设该节点的编号为 xx):

先将 xx 的左右儿子合并,然后自底向上更新 distdist,若不满足左偏性质则交换左右儿子,当 distdist 无需更新时结束递归。

这样做可以证明时间复杂度是 O(logn)O(\log n) 的。

如果是下面这种做法:

直接将 xx 的左右儿子合并,合并后的节点再与 xx 所在的集合的堆顶合并。

这样做的时间复杂度是多少呢?

2021/5/18 21:59
加载中...