打印在O（K *日志（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 *日志（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个元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！