A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor
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??
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
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.
HeapEle FindKthEle( int k )
HeapEle he;//it is a heap element;
while( true )
he=HA.ExtractMin()//return the minimum element and delete it from the HA heap
if( rank==k )
HA.Insert(he.Left);//insert the left and right children in HO into the HA
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
Tuesday, February 12, 2008
This topic is archived. No further replies will be accepted.Other recent topics
Powered by FogBugz