鉴于以下问题，我不完全确定我当前的解决方案：
问题 ：
给定一个包含元素的最大堆n，它存储在一个数组A中，是否可以打印所有最大的K元素O(K*log(K))？
我的回答：
是的，它是，因为搜索一个元素需要O(log(K))，因此这样做
forK元素需要 O(K * log(K))运行时间。
问问题
15344 次
5 回答
17
在大小为 N 的堆中搜索元素不是 O(K)。首先，查找一个元素的时间复杂度取决于您尝试提取的元素数量（这就是 K 表示的）是没有意义的。此外，没有在堆中搜索这样的事情——除非您将标准的查看每个元素的搜索计算在 O(N) 中。
然而，在堆中找到最大的元素是 O(1) 设计的（我显然假设它是一个最大堆，所以最大元素在堆的顶部），并从堆中删除最大的元素大小 N 为 O(log(N)) （将其替换为叶元素，并让该叶从堆中向下渗透）。
因此，从堆中提取 K 个元素，并返回未提取元素的堆，将花费 O(K·log(N)) 时间。
如果从堆中非破坏性地提取 K 个元素会发生什么？您可以通过保留堆堆来做到这一点（其中堆的值是其最大元素的值）。最初，这个堆只包含一个元素（原始堆）。要提取下一个最大元素，请提取顶部堆，提取其顶部元素（即最大值），然后将两个子堆重新插入堆中。
这会在每次删除时将堆堆增加一个（删除一个，添加两个），这意味着它永远不会容纳超过 K 个元素，因此 remove-one-add-two 将花费 O(log(K) ）。迭代这个，你会得到一个实际的 O(K·log(K)) 算法，它确实返回了前 K 个元素，但无法返回未提取元素的堆。
于 2012-06-26T14:36:24.437 回答
11
这在最大堆中是可能的，因为您只是从树中打印元素，而不是提取它们。
首先确定位于根节点的最大元素。形成一个指向节点的指针并将其添加到一个空的“最大值”列表中。然后，对于每个k值，循环执行以下步骤。
- 从列表中弹出最大元素，取 O(1)。
- 打印它的值，取 O(1)。
- 将此最大元素的每个子元素插入到列表中。插入时保持排序，花费 O(log(size of list)) 时间。这个列表的最大大小，因为我们正在执行这个循环 k 次，是 branch-size*k。因此，这一步需要 O(log(k)) 时间。
总而言之，运行时间为 O(klog(k))，根据需要。
于 2012-06-26T15:38:28.407 回答
11
我发现其他答案令人困惑，所以我决定用一个实际的示例堆来解释它。假设原始堆大小为 N，并且您想找到第 k 个最大的元素，该解决方案需要 O(klogk) 时间和 O(k) 空间。
10
/ \
5 3
/ \ /\
4 1 2 0
Original Heap, N = 7
想找到第五大元素。k = 5 注意：在新堆中，需要存放指向原堆的指针。这意味着，您不会删除或更改原始堆。原始堆是只读的。因此，您永远不必执行任何需要 O(logN) 时间的操作。
设 x' 是指向原始堆中值 x 的指针。
第一次迭代：将根节点的指针放入新堆
步骤 1：添加指向节点 10 的指针
10'
New Heap, size = 1, root = 10', root->left = 5, root right->3
打印第一个最大的元素 = 10
第二次迭代：参考原始堆并将其两个子代插入新堆。（存储指向它们的指针而不是值本身）。您要存储指针的原因是，您可以稍后在 O(1) 中从原始堆访问它们以搜索它们的子代，而不是 O(N) 来搜索该值在原始堆中的位置。
Step 2a：从原堆中寻找新堆根节点的左子节点。将左孩子的指针（在本例中为 5'）添加到新堆。
10'
/
5'
New Heap, size = 2, root = 10', root->left = 5, root right->3
步骤 2b：从原始堆中寻找新堆根节点的右子节点。将左孩子的指针（在本例中为 3'）添加到新堆。
10'
/ \
5' 3'
New Heap, size = 3, root = 10', root->left = 5, root right->3
步骤 2c：从新堆中删除根节点。（用最右边的叶子交换最大节点，删除根节点并向下冒泡当前根以保持堆属性）
10' swap 3' remove & bubble 5'
/ \ => / \ => /
5' 3' 5' 10' 3'
New Heap, size = 2, root = 5', root->left = 4, root right->1
打印第二大元素 = 5
Step 3a：从原堆中寻找新堆根节点的左子节点。将左孩子的指针（在本例中为 4'）添加到新堆。
5'
/ \
3' 4'
New Heap, size = 3, root = 5', root->left = 4, root right->1
Step 3b：从原堆中寻找新堆根节点的右孩子。将左孩子的指针（在本例中为 1'）添加到新堆。
5'
/ \
3' 4'
/
1'
New Heap, size = 4, root = 5', root->left = 4, root right->1
步骤 3c：从新堆中删除根节点。（将新堆的最大节点（5'）与其最右边的从新堆的原始堆（1'）交换，删除根节点并向下冒泡当前根以保持堆属性）
5' Swap 1' remove & bubble 4'
/ \ => / \ => / \
3' 4' 3' 4' 3' 1'
/ /
1' 5'
New Heap, size = 3, root = 4', root->left = NULL, root right->NULL
打印第三大元素 = 4
步骤 4a 和步骤 4b 什么都不做，因为在这种情况下，根节点没有来自原始堆的任何子节点。
步骤 4c：从新堆中删除根节点。（用最右边的叶子交换最大节点，删除根节点并向下冒泡当前根以保持新堆中的堆属性）
4' Swap 1' remove & bubble 3'
/ \ => / \ => /
3' 1' 3' 4' 1'
New Heap, size = 2, root = 3', root->left = 2, root right->0
打印第 4 大元素 = 3
Step 5a：从原堆中寻找新堆根节点的左子节点。将左孩子的指针（在本例中为 2'）添加到新堆。
3'
/ \
1' 2'
New Heap, size = 3, root = 3', root->left = 2, root right->0
步骤 5b：从原始堆中寻找新堆根节点的右子节点。将左孩子的指针（在本例中为 0'）添加到新堆。
3'
/ \
1' 2'
/
0'
New Heap, size = 4, root = 3', root->left = 2, root right->0
步骤 5c：从新堆中删除根节点。（将最大节点（3'）与新堆中原始堆（即0'）的最右边离开，删除根节点并向下冒泡当前根以保持新堆中的堆属性）
3' Swap 0' Remove & Bubble 2'
/ \ => / \ => / \
1' 2' 1' 2' 1' 0'
/ /
0' 3'
New Heap, size = 3, root = 2', root->left = NULL, root->right = NULL
打印第 5 个最大元素 = 2
最后，由于我们经历了 k 次迭代，k = 5。我们现在可以从新堆中提取根元素的值。在这种情况下，值为 2。因此，我们从原始堆中找到了第 k 个最大值。
时间复杂度，T(N,k) = O(klogk) 空间复杂度，S(N,k) = O(k)
希望这可以帮助！
顺志龙，
多伦多大学。
于 2015-09-14T06:49:22.250 回答
4
It is a simple and elegant algorithm to get first k elements of a max heap in k log(k) time.
steps:-
1.construct another max heap name it auxiliary heap
2.add root element of main heap to auxiliary heap
3.pop out the element from auxiliary heap and add it's 2 children to the heap
4.do step 2 and 3 till k elements have been popped out from auxiliary heap. Add the popped element's children to the auxiliary heap.
于 2013-06-30T12:47:13.540 回答
3
确实，这太容易了，提取最大元素就是O(log(N))堆N的大小。和N≠K。
我将添加搜索随机元素 isO(N)和 not O(Log(N))，但在这种情况下，我们要提取最大值。
于 2012-06-26T14:31:38.730 回答