O（klogk）时间算法从二进制堆中查找第k个最小元素

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

O(klogn)是显而易见的，但找不到O(klogk)一个。不确定，也许我们可以使用第二堆。

好吧，您的直觉是正确的，我们需要额外的数据结构来实现O（klogk），因为如果我们仅对原始堆执行操作，则术语logn仍将保持复杂性。

从目标复杂度O（klogk）进行猜测，我觉得需要创建和维护大小为k的堆来帮助我实现目标。如您所知，以自上而下的方式构建大小为k的堆需要O（klogk），这确实使我想起了我们的目标。

以下是我尝试获得O（klogk）的尝试（不一定优雅或有效）：

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

时间复杂度：在每次迭代中，需要O（3logk）时间才能从中删除一个元素并将两个元素插入新堆中。经过k次迭代，它是O（3klogk）= O（klogk）。

希望这个解决方案能给您带来启发。