在 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屋！