我们有一个n节点二进制堆,它包含n不同的项(根目录下的最小项).对于a k<=n,找到O(klogk)时间算法以kth从堆中选择最小元素.
O(klogn)显而易见,但无法找出O(klogk)一个.也许我们可以使用第二堆,不确定.
鉴于以下问题,我不能完全确定我目前的解决方案:
题 :
给定n存储在数组中的元素的最大堆A,是否可以打印所有最大的K元素O(K*log(K))？
我的回答:
是的,因为搜索元素需要O(log(K)),因此这样做
为K元素将需要 O(K * log(K))运行时间.