Creating a sorted array from the smallest log n tems in a heap

Question

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 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.

I'd appreciate any help, thanks.

Answer 1

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.

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))

Answer 2

The following "pseudocode", runs in O(mlogn) where m is the number of items in the heap. This number surely influences the running time, but I suppose you only care about the variation versus the number of items you want to store.

std::vector<heapItem*> myVect;
for each heap-item* p
{ 
  bool inserted = false;
  for(auto it= myVect.begin(); (it!=myVect.end()) && !inserted; ++it)
  { 
    if(p->itemSize > (*it).itemSize)
    {
      myVect.insert(it, p);
      inserted=true;
    }
  }
  if((myVect.size() < logn) && !inserted)
     myVect.push_back(p);
  else if(myVect.size() > logn)
     myVect.resize(logn);
}