鉴于以下问题,我不确定当前的解决方案:
题 :
给定具有n存储在数组中的元素的最大堆A,是否可以打印其中的所有最大K元素O(K*log(K))?
n
A
K
O(K*log(K))
我的回答 :
是的,是的,因为搜索元素需O(log(K))要这样做,因此
O(log(K))
因为K元素会花费 O(K * log(K))运行时间。
O(K * log(K))
在最大堆中这是可能的,因为您仅从树中打印元素,而不提取它们。
首先确定最大元素,该元素位于根节点。形成一个指向节点的指针,并将其添加到否则为空的“最大”列表中。然后,对于每个k值,循环执行以下步骤。
k
因此,根据需要,总的运行时间为O(klog(k))。