techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Finding kth smallest elements in a min heap O(k log k)

Hi, whats the best approach for finding the kth smallest elements (a sorted list of them from smallest to highest) on a min-heap with n elements in O(k log k) time.
 

I can see how to do it in n log k time..and obviously in n log k time.. but how in k log k time??
Kevin McNally Send private email
Monday, February 11, 2008
 
 
Well, I know a O(klog n) method.

(no language assumed)
kth-largest(heap, k)
{
 for(int i=0;i<k-1;i++)
  extract-min(heap);
 return extract-min(heap)
}

Cant figure out any klogk algo though
jigsaw Send private email
Monday, February 11, 2008
 
 
yeah I meant originally that k log n is the obvious one. can figure out n log k ..but not k log k

Monday, February 11, 2008
 
 
If you want to get fancier than a min heap, there are priority queues where extract_min() is O(1).  Either add_item or extract_min can be O(1), if the other is O(log(n)).
Skorj Send private email
Monday, February 11, 2008
 
 
For solving this problem, we must have another min heap.

Assume that the original min-heap is called HO and the auxiliary min-heap is named HA.

Initially, the element at the top of HO, the minimum one, is inserted into the HA. However, here we dont do the operation of extract-min with HO. HeapEle is the data structure for the elements in the heap.

Heap HO;
Heap HA;
HeapEle FindKthEle( int k )
{
    HeapEle he;//it is a heap element;
    int rank=1;
    HA.Insert(HO.min);
    while( true )
    {
        he=HA.ExtractMin()//return the minimum element and delete it from the HA heap
        if( rank==k )
        {
          return he;
        }
        else
        {
          rank++;
          HA.Insert(he.Left);//insert the left and right children in HO into the HA
          HA.Insert(he.Right);
        }
    }
}

Every while-loop the "rank"th smallest element can be gotten. So we need k loops to get the kth smallest elements. Because the size of the auxiliary heap is always less than k, actaully every while-loop the size of the auxiliary heap increases by one, and the original heap HO has no operation during the finding, the running time is O(klgk)
hearmin Send private email
Tuesday, February 12, 2008
 
 
thx alot, great algoritm.. its always seems so simple after ur shown the answer :). thanks again

Tuesday, February 12, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz