RSS Feed

techInterview Discussion

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

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

yeah I meant originally that k log n is the obvious one. can figure out n log k ..but not k log k

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

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)

thx alot, great algoritm.. its always seems so simple after ur shown the answer :). thanks again