O（klogk）时间的算法找出从二元堆第k个最小元素 [英] O(klogk) time algorithm to find kth smallest element from a binary heap
问题描述
我们有一个n节点二叉堆，其中包含n个不同的项目（最小的项目在根目录）。对于K＆LT; = N，找一个O（klogk）时间的算法来选择从堆中第k个最小元素
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屋！
