问题描述
由于以下问题，我不能完全肯定我目前的解决方案：
Given the following problem , I'm not completely sure with my current solution :
问：
给出一个最大堆与 N 元素，它存储在一个数组 A ，是有可能的打印所有的最大的 K 在元素O（K *日志（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（日志（K）），因此这样做
Yes , it is , since searching an element requires O(log(K)) , hence doing that
为 K 元素将采取 O（K *日志（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时间（日志列表）（尺寸）。该列表的最大大小，因为我们在执行这个循环k次，是分支尺寸* K。所以这一步需要O（日志（k））的时间。
在总的话，运行时间为O（KLOG（k））的，根据需要
In total, then, the run time is O(klog(k)), as desired.
这篇关于打印在O（K *日志（K））在给定的堆最大的k个元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！