我们有一个 n 节点二叉堆，其中包含n不同的项目（根部的最小项目）。为一个k<=n， 发现O(klogk)时间算法选择kth堆中的最小元素。
O(klogn)很明显，但无法找出O(klogk)一。也许我们可以使用第二个堆，但不确定。
好吧，你的直觉是正确的，我们需要额外的数据结构来实现 O(klogk)，因为如果我们只是在原始堆上执行操作，则 logn 项将保留在最终的复杂度中。
从目标复杂度 O(klogk) 猜测，我想创建并维护一个大小为 k 的堆来帮助我实现目标。您可能知道，以自上而下的方式构建大小为 k 的堆需要 O(klogk)，这确实让我想起了我们的目标。
以下是我尝试达到 O(klogk) 的尝试（不一定优雅或高效）：
我们创建一个新的最小堆，并将其根初始化为原始堆的根。
我们通过删除当前根并将当前根的两个子代插入到原始堆中来更新新的最小堆。我们重复这个过程 k 次。
生成的堆将由 k 个节点组成，其根是原始堆中第 k 个最小的元素。
注意：新堆中的节点应该存储原始堆中对应节点的索引，而不是节点值本身。在步骤 2 的每次迭代中，我们实际上将一个又一个节点的网络添加到新堆中（一个删除，两个插入），其中 k 次迭代将产生大小为 k 的新堆。第i次迭代时，要删除的节点是原堆中第i个最小的元素。
时间复杂度：在每次迭代中，从新堆中删除一个元素并向新堆中插入两个元素需要 O(3logk) 时间。经过 k 次迭代后，O(3klogk) = O(klogk)。
希望这个解决方案对您有所启发。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
