recategorized by
3,892 views
8 votes
8 votes
In a min-heap with n elements

1).  The 7th smallest element can be found in time, if duplicates are allowed ?

2).  The 7th distinct smallest element can be found in time, If duplicates are allowed ?
recategorized by

3 Answers

1 votes
1 votes
For first one :

O(log n)

Reason : To delete an element , it takes O(1), then we have to heapify , which takes O(log n);

Now for 7th smallest element, we need 7 such operations, hence O(7 log n) = O(log n)

For 2nd one :

O(n)
0 votes
0 votes

It will take O(1)

    

0 votes
0 votes
for first question it is O(log n) deletion in a min heap also does heapify  after deletion  so it is O(log n) ...correct me if i am wrong

Related questions

1 votes
1 votes
1 answer
1
11 votes
11 votes
5 answers
3
Vikrant Singh asked Dec 28, 2014
3,611 views
What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap?$\Theta(1)$$\Theta (\log n)$$\Theta (n)$$\Theta (n \log n)$
1 votes
1 votes
1 answer
4
gmrishikumar asked Dec 1, 2018
2,248 views
What is the time complexity to find the Kth largest element in a Min-Heap? Or equivalently, What is the time complexity to find Kth smallest element in Max-Heap?