从二叉堆中查找第 k 个最小元素的 O(klogk) 时间算法

Question

我们有一个 n 节点二叉堆，其中包含 n 个不同的项（根部的最小项）。对于k<=n，找到一个O(klogk)时间算法来从堆中选择kth最小的元素。

O(klogn) 很明显，但无法找出 O(klogk) 。也许我们可以使用第二个堆，但不确定。

Answer 1

好吧，你的直觉是正确的，我们需要额外的数据结构来实现 O(klogk)，因为如果我们只是在原始堆上执行操作，则 logn 项将保留在最终的复杂性中。

从目标复杂度 O(klogk) 猜测，我想创建并维护一个大小为 k 的堆来帮助我实现目标。您可能知道，以自上而下的方式构建大小为 k 的堆需要 O(klogk)，这确实让我想起了我们的目标。

以下是我尝试达到 O(klogk) 的尝试（不一定优雅或高效）：

1. 我们创建一个新的最小堆，将其根初始化为原始堆的根。

2. 我们通过删除当前根并将当前根的两个子代插入到原始堆中来更新新的最小堆。我们重复这个过程 k 次。

3. 生成的堆将由 k 个节点组成，其根是原始堆中第 k 个最小的元素。

注意：新堆中的节点应该存储原始堆中对应节点的索引，而不是节点值本身。在步骤 2 的每次迭代中，我们实际上将一个又一个节点的网络添加到新堆中（一个删除，两个插入），其中 k 次迭代将产生大小为 k 的新堆。第i次迭代时，要删除的节点是原堆中第i个最小的元素。

时间复杂度：在每次迭代中，从新堆中删除一个元素并向新堆中插入两个元素需要 O(3logk) 时间。经过 k 次迭代后，O(3klogk) = O(klogk)。

希望这个解决方案对您有所启发。

Answer 2

假设我们使用最小堆，因此根节点始终小于其子节点。

Create a sorted list toVisit, which contains the nodes which we will traverse next. This is initially just the root node.
Create an array smallestNodes. Initially this is empty.
While length of smallestNodes < k:
    Remove the smallest Node from toVisit
    add that node to smallestNodes
    add that node's children to toVisit

完成后，第 k 个最小节点位于smallestNodes[k-1] 中。

根据 toVisit 的实现，您可以在 log(k) 时间内插入并在常数时间内删除（因为您只删除最顶层的节点）。这使得总共 O(k*log(k)) 。