algorithm - RB树和堆之间的大O作为排序集

Question

如果我们基于 RB Tree 和 Heap 构造排序集。执行 insert() 和 deleteMax() n 次。

(1)。什么是大O？

我的想法：对于 RB 树和堆，deleteMax() 和插入() 都将采用 nlog(n)，这是否意味着时间复杂度将为 O(nlog(n) + nlog(n)) = O(2nlog (n)) ?

(2)。他们的常数因子的差异如何。

Answer 1

假设您正在谈论二进制堆。对于每个插入/最大删除，时间复杂度是O(log(n))针对 RB 和二进制堆的，其中n是 RB/堆中现有元素的数量。斐波那契堆具有更好的理论时间复杂度。你应该阅读维基。

至于常数，二叉堆优于RB。它也更容易实现并且占用更少的空间。当您只想跟踪最小/最大值而不需要知道所有元素的完整顺序时，您应该使用堆。