## techInterview Discussion |
||

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

Powered by FogBugz