max - 您将使用哪些操作来实现具有入队和出队的优先队列 PQ？

Question

假设您正在实现一个优先队列 PQ，它在出队操作时返回最大元素。如果我们使用最大堆来实现 PQ，入队是 O(______) 操作，出队是 O(____) 操作

有人可以回答/解释你是如何得到它的......我在想两者都登录但不确定？

标签： maxpriority-queuemax-heapenqueue

Answer 1

想想二叉堆是如何工作的。

插入项目时，将其添加为堆的最后一个节点，然后将其筛选到适当的位置。由于包含 n 个项目的堆的高度为 log(n)，并且您可能必须将项目一直筛选到顶部，因此最坏的情况是 O(log n)。

当您删除一个项目时，您将根注释替换为堆中的最后一个节点，然后将其向下筛选。最坏的情况是，您必须将它一直筛选到堆的底部：移动 log(n) 级别。因此，O(log n)。