在 O(K*log(K)) 中打印给定堆中最大的 K 个元素? [英] Print the biggest K elements in a given heap in O(K*log(K))?
问题描述
鉴于以下问题,我不完全确定我当前的解决方案:
Given the following problem , I'm not completely sure with my current solution :
问题:
给定一个包含 n
个元素的最大堆,它存储在一个数组 A
中,是否可以打印所有最大的 K
个元素在 O(K*log(K))
中?
Given a maximum heap with n
elements , which is stored in an array A
, is it possible to print all the biggest K
elements in O(K*log(K))
?
我的回答:
是的,因为搜索元素需要 O(log(K))
,因此这样做
Yes , it is , since searching an element requires O(log(K))
, hence doing that
对于 K
元素需要 O(K * log(K))
运行时间.
for K
elements would take O(K * log(K))
running time.
推荐答案
这在最大堆中是可能的,因为您只是从树中打印元素,而不是提取它们.
This is possible in a max-heap because you are only printing elements from the tree, not extracting them.
首先识别位于根节点的最大元素.形成指向节点的指针并将其添加到否则为空的最大值"列表中.然后,对于每个 k
值,循环执行以下步骤.
Start by identifying the maximum element, which is located at the root node. Form a pointer to a node and add it to an otherwise empty "maximums" list. Then, for each of the k
values, perform the following steps in a loop.
- 从列表中弹出最大元素,取 O(1).
- 打印其值,取 O(1).
- 将这个最大元素的每个子元素插入到列表中.插入时保持排序,花费 O(log(size of list)) 时间.这个列表的最大大小,因为我们要执行这个循环 k 次,是 branch-size*k.因此这一步需要 O(log(k)) 时间.
那么,总而言之,运行时间是 O(klog(k)),根据需要.
In total, then, the run time is O(klog(k)), as desired.
这篇关于在 O(K*log(K)) 中打印给定堆中最大的 K 个元素?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!