堆插入，删除k个元素

Question

我有以下问题(我认为这是众所周知的/标准的)，我正在思考：

验证在二进制最小堆中列出k个最小元素是否为O(k)。

我在考虑在BFS中遍历大的最小堆，维护一个最小堆而不是简单的队列。最初，辅助min-heap包含我的大min-heap的根。在每一步，我提取最小值并添加它的所有子元素(最大值2)。在辅助min-heap上执行k次提取-min之后，算法停止。辅助min-heap的大小为O(k) (对于提取的每个min-key，我插入其子项，最大值为2)。

问题是extract-min的复杂度为O(log )，因此该算法的复杂度为O( k )。我必须在O(k)中找到一个。

你有什么想法/论文可以让我用吗？

谢谢!

Answer 1

我想我找到解决方案了。在每个步骤中，我不执行extract-min，而是执行increase-key。我搜索了一个数据结构，它的增量键、插入键和get-min的最坏情况时间为O(1)，我找到了。

有关更多信息，您可以查看Fibonacci heap，因为Brodal队列基于斐波那契堆开发的概念。

因此，在每个步骤中，我都有以下操作序列：

get堆min=get-min(辅助堆)get

• (v1，v2)是v1)

• insert(Auxiliary堆，，

1. ，v2的子堆)

这4种操作中的每一种都具有O(1)最坏情况的复杂度。

Answer 2

在谷歌上搜索“堆选择算法”，我偶然发现了“Frederickson的堆选择算法”，它指向this paper (27页...)。