我正在考虑以下问题（我认为这是众所周知的/标准）：
验证在二进制最小堆中列出 k 个最小元素是 O(k)。
我正在考虑遍历BFS中的大最小堆，维护一个最小堆而不是一个简单的队列。最初，辅助最小堆包含我的大最小堆的根。在每个步骤中，我提取最小值并添加其所有子项（最多 2 个）。该算法在辅助最小堆上的 k 个提取分钟后停止。辅助最小堆的大小是 O(k)（对于提取的每个最小键，我插入它的孩子，最大 2）。
问题是 extract-min 具有 O(log k) 复杂度，因此该算法具有 O(k log k) 复杂度。我必须在 O(k) 中找到一个。
你有什么我可以使用的想法/论文吗？
谢谢！
谷歌搜索“堆选择算法”，我遇到了“Frederickson 的堆选择算法”，这导致了这篇论文（27 页......）。
我想我找到了解决方案。在每一步，我不执行 extract-min，而是执行 increase-key。我搜索了一个数据结构，对于增加键、插入键和 get-min 具有 O(1) 最坏情况时间，我找到了Brodal queue。
有关更多信息，您可以查看Fibonacci heap，因为 Brodal 队列基于 Fibonacci heap 开发的概念。
因此，在每个步骤中，我都有以下操作序列：
min = get-min(辅助堆)
让 (v1, v2) 成为 min 的孩子
增加最小（辅助堆，根，v1）
插入（辅助堆，v2）
这 4 个操作中的每一个都具有 O(1) 的最坏情况复杂度。