RT。
左偏树删除任意节点时(设该节点的编号为 xxx):
先将 xxx 的左右儿子合并,然后自底向上更新 distdistdist,若不满足左偏性质则交换左右儿子,当 distdistdist 无需更新时结束递归。
这样做可以证明时间复杂度是 O(logn)O(\log n)O(logn) 的。
如果是下面这种做法:
直接将 xxx 的左右儿子合并,合并后的节点再与 xxx 所在的集合的堆顶合并。
这样做的时间复杂度是多少呢?