algorithm - 破碎优先级队列的算法

Question

IF 优先级队列有两个操作：insert和broken_min。Wherebroken_min返回第一个或第二个最小项。

这些都不能在 o(logn) 时间内实现。我认为这是因为 insert 使用了 broken_min ，然后必须进行更多检查以查看它是否具有最大值。

这是正确的推理吗？

Answer 1

是的，我相信你是对的。

优先级队列通常实现为堆：

堆是一种专门的基于[二进制]树的数据结构......父节点的键小于或等于子节点的键，最低的键在根节点（最小堆）中。

broken_min可以在 O(1) 中实现，因为其中一个子元素将是第二大元素，所以我们可以同时检查两者。

但是insert会取 Ω(log n)，这不是 o(log n)（但确实是 O(log n)）。

我怀疑你会找到一个可以满足给定运行时间的优先级队列实现，但是说它不可能是不负责任的。

注意：我假设你的意思是给定标签的 little-o（一个严格的上限，而不是 big-O，这是一个更大或等于上限），尽管大部分时间都使用 big-O，而且很少-o 几乎从未使用过（据我所知）。