Jan 6, 2009

What’s the best approach for finding the kth smallest elements on a min-heap with n elements in O(k log k) time. Assume that the original min-heap is

What’s the best approach for finding the kth smallest elements on a min-heap with n elements in O(k log k) time.
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 do not 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++;//each time insert two elements and get one ‘rank’th element, so the number of elements in the min heap is from 1,2…15
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)

No comments:

Post a Comment