algorithm - 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)的尝试(不一定优雅或有效):

我们创建一个新的min堆，将其根初始化为原始堆的根。

我们通过删除当前根并在原始堆中插入当前根的两个子级来更新新的min堆。我们重复此过程k次。

结果堆将包含k个节点，其根是原始堆中第k个最小的元素。

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

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

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