本文介绍了打印在O(K *日志(K))在给定的堆最大的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个元素?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 09:06