IITD phd-sample Q

Question

You are given a heap containing N elements. Write a procedure which takes as input a parameter k, and outputs the k'th smallest number in the heap. The running time of the procedure must depend on k alone.

Comments

I assume you mean min-heap.
kth smallest element will surely be present in first k levels. In worst case it can be at $k^{th}$ level. So, search all elements till that level.

Answer 1

I'd advice u to meet thelink given below. It'll for sure answer your question. The explanation is indeed very good. Consider visiting once. Hope it helps u. :)

http://algorithms.tutorialhorizon.com/binary-min-max-heap/

Comments

Thanks a lot