O(klogk) 时间算法从二叉堆中找到第 k 个最小元素 [英] O(klogk) time algorithm to find kth smallest element from a binary heap
问题描述
我们有一个 n 节点的二进制堆，其中包含 n 个不同的项目(根中最小的项目).对于k<=n，找到一个O(klogk)时间算法从堆中选择kth个最小元素.
We have an n-node binary heap which contains n distinct items (smallest item at the root). For a k<=n, find a O(klogk) time algorithm to select kth smallest element from the heap.
O(klogn) 是显而易见的，但无法找出 O(klogk) 之一.也许我们可以使用第二个堆，不确定.
O(klogn) is obvious, but couldn't figure out a O(klogk) one. Maybe we can use a second heap, not sure.
推荐答案
嗯，你的直觉是对的，我们需要额外的数据结构来实现 O(klogk) 因为如果我们只是在原始堆上执行操作，术语 logn 将保持在由此产生的复杂性中.
Well, your intuition was right that we need extra data structure to achieve O(klogk) because if we simply perform operations on the original heap, the term logn will remain in the resulting complexity.
从目标复杂度 O(klogk) 猜测，我想创建和维护一个大小为 k 的堆来帮助我实现目标.您可能知道，以自顶向下的方式构建大小为 k 的堆需要 O(klogk)，这让我想起了我们的目标.
Guessing from the targeted complexity O(klogk), I feel like creating and maintaining a heap of size k to help me achieve the goal. As you may be aware, building a heap of size k in top-down fashion takes O(klogk), which really reminds me of our goal.
以下是我试图达到 O(klogk) 的尝试(不一定优雅或高效):
The following is my try (not necessarily elegant or efficient) in an attempt to attain O(klogk):
我们创建一个新的最小堆，将其根初始化为原始堆的根.
We create a new min heap, initializing its root to be the root of the original heap.
我们通过删除当前根并在原始堆中插入当前根的两个孩子来更新新的最小堆.我们重复这个过程 k 次.
We update the new min heap by deleting the current root and inserting the two children of the current root in the original heap. We repeat this process k times.
生成的堆将由 k 个节点组成，其根是原始堆中第 k 个最小的元素.
The resulting heap will consist of k nodes, the root of which is the kth smallest element in the original heap.
注意:新堆中的节点应该存储它们在原始堆中对应节点的索引，而不是节点值本身.在第 2 步的每次迭代中，我们确实将一个节点的网络添加到新堆中(一个删除，两个插入)，其中 k 次迭代将产生大小为 k 的新堆.在第 i 次迭代中，要删除的节点是原堆中第 i 个最小的元素.
Notes: Nodes in the new heap should store indexes of their corresponding nodes in the original heap, rather than the node values themselves. In each iteration of step 2, we really add a net of one more node into the new heap (one deleted, two inserted), k iterations of which will result in our new heap of size k. During the ith iteration, the node to be deleted is the ith smallest element in the original heap.
时间复杂度:在每次迭代中，从新堆中删除一个元素并将两个元素插入新堆需要 O(3logk) 时间.k次迭代后，就是O(3klogk) = O(klogk).
Time Complexity: in each iteration, it takes O(3logk) time to delete one element from and insert two into the new heap. After k iterations, it is O(3klogk) = O(klogk).
希望这个解决方案对您有所启发.
Hope this solution inspires you a bit.
这篇关于O(klogk) 时间算法从二叉堆中找到第 k 个最小元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
