从堆中最小的log n tems创建排序数组

Question

给定二进制堆,我需要在O(log n loglog n)中创建一个包含堆中最小log n项的排序数组.

当然我尝试了删除最小日志n次的天真方法,但是需要O(log ²(n)).我不知道如何改进.

我很感激任何帮助,谢谢.

Answer 1

只需对堆进行贪婪搜索,将其解释为一般二叉树.堆不变意味着当你知道k堆中最小的项时,最小的项k+1必须是它们的一个子项.您可以为下一个最小的项构建所有候选项的第二个堆,并且该堆永远不会超出O(log(n)),因此插入和删除需要O(log(log(n)),并且您需要O(log(n))在第二个堆中插入和删除.这适用k于O(k*log(k))及时查找堆中的最小项,而不管是什么k.

这是Python中的示例代码:

import heapq

def smallestk(heap, k):
    if not k:
        return
    candidates = [(heap[0], 0)]
    for _ in xrange(k):
        val, index = heapq.heappop(candidates)
        yield val
        for child in (2*index+1, 2*index+2):
            if child < len(heap):
                heapq.heappush(candidates, (heap[child], child))