recategorized by
809 views
4 votes
4 votes

The time complexity of the best known algorithm to find $p^{th}$ ${\left ( p<n \right )}$ smallest element from a $minheap$ of $n$ elements is _______.

  1. $\Theta\left ( p\log p \right )$
  2. $\Theta\left ( p\log n \right )$
  3. $\Theta\left ( pn \right )$
  4. $\Theta\left ( n\log p \right )$
recategorized by

3 Answers

Best answer
8 votes
8 votes
Since every time when we delete an element from the heap, we put the lower right-most element to the root and then apply Heapify( ) {i.e Adjusting Heap} on the whole heap, So now remaining element in the heap will be one less from the previous state of the heap. So for each Heapify(  ), it should take O(log n). Here n is remaining element in the Heap. So for 'P' delete operation, it should take $O (p \log n)$.
selected by
2 votes
2 votes
we know that both cases have been covered in duplicates keys and distinct keys

Assume root is at first level and height of root is $0$.

the first min can be found at most on the first level, 2$^{nd}$ min can be found at most on the second level, 3$^{rd}$min can be found at most on the third level...... so pth min element can be found at pth level.similarly, on deleting the pth min, we got a pth minimum $( p<n )$ which we want.

So I need not search in full tree.

on deleting root, we got the first min.then again adjust heap then again deleting root, we got the second min and then adjust heap.

and so on we do this by deleting pth root element of the tree we got a pth minimum value.

So I have to apply this operation p times and each operation will take $0$$\left ( \log p \right )$Otime.

So overall time complexity will be : $0$$\left ( p\log p \right )$
edited by
1 votes
1 votes

1st smallest can be found in at most 0th height i.e, 1st element.

2nd smallest can be found in at most 1st height i.e, within 3 elements.

3rd smallest can be found in at most 2nd height i.e, within 7 elements.

similarly pth smallest can be found in at most (p-1)th height i.e, 2p-1 elements.

To extract pth smallest we need to do min heap operation p times.

So, p*log(2p) = O(p2)

AM I CORRECT ?

Answer:

Related questions