根据堆中最小的日志项创建排序的数组 [英] Creating a sorted array from the smallest log n tems in a heap

问题描述

给定一个二进制堆，我需要在O（log n loglog n）中创建一个包含最小堆n项的排序数组。

Given a binary heap, I need to create a sorted array containing the smallest log n items from the heap, in O(log n loglog n).

Of当然，我尝试了删除n次最小日志的天真的方法，但这需要O（log ² （n））。我不知道该如何改善。

Of course I tried the naive approach of deleting the minimum log n times, but that takes O(log²(n)). I don't know how to improve that.

感谢您的帮助。

推荐答案

只需对堆进行贪婪的搜索，就可以解释为一般的二叉树。堆不变性意味着，当您知道堆中最小的 k 项时，必须将 k + 1 个最小的项成为他们的孩子之一。您可以为第二个最小的项目构建第二个所有候选对象的堆，并且该堆永远不会增长到 O（log（n））以上，因此插入和删除操作需要 O（log（log（n）），并且您需要在其中插入和删除 O（log（n））第二个堆。这用于在 O（k * log（k））中查找堆中最小的 k 项时间，无论 k 是什么。

Just run a greedy search of the heap, interpreted as a general binary tree. The heap invariant means that when you know the smallest k items of the heap, the k+1th-smallest must be one of their children. You can build a second heap of all candidates for the next-smallest item, and that heap will never grow beyond O(log(n)), so insertions and deletions take O(log(log(n)), and you need O(log(n)) insertions and deletions in the second heap. This works for finding the smallest k items of a heap in O(k*log(k)) time, regardless of what k is.

以下是Python中的示例代码：

Here's example code in 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))

这篇关于根据堆中最小的日志项创建排序的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！