In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time
@ Digvijay Pandey "In a heap with n elements with the smallest element at root"
It can go only till the 7th level. So, the number of checks is bounded by 2^{7 }= 127.
Why is this 2 ^{n }-1?
Suppose in a min heap of height 2,we can find the second min in max 2 comparisons.Plz explain anyone
I think ans is o(1), correct but following logic u came up with is wrong. We can find second smallest in only 1 comparision, 3rd smallest requires 2 more comparisions.
In order to find the 7 th element one must remove elements one by one from the heap, until the 7 th smallest element is found. As a heap may contain duplicate values, we may need to remove more then 7 elements. At the worst case we will have to remove all n elements. 1 deletion takes O(log(n)). Hence ‘n’ deletes will take O(nlog(n)).
Ref:Question No.36.http://www.nid.iitkgp.ernet.in/DSamanta/courses/IT60101_2/Archives/Assignment-%20IC%20Binary%20Trees%20Solutions.pdf
There is no question 36 or I cannot see Questions after 27.
And see this http://algs4.cs.princeton.edu/24pq/
It says priority queue (which indeed min/max heap ) with duplicate gives any one of largest value for delete_max () operation
So similarly for min heap with duplicate elements it will perform deletemin operation 7 times and each time within logN time it will give minmum element of the min heap. LogN will be taken for heapify.
Taking into consideration what you said then there should be a method to compare previously deleted element with newly deleted element to be sure that both are not identical. And you get truly 7th smallest element (if exists)
@learncp @Ajay Choudhary 1
Link provided by you is not working please make it correct.
Key point: The k^{th} smallest element cannot be deeper than the k^{th} level of the heap, since the path from it to the root must go through elements of decreasing value.
@Sachin Mittal 1 If input is like 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 3 4, Now we want to find 3rd smllest then your statement will become False. Please correct me if i am wrong?
if question is about to find n^{th} smallest element then it will be O(n)???????