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

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

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

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

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

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

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

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

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

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

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