Log In
0 votes

My question is in Question like find 5th Smallest element in a heap:

It requires O(logn) time if we do only Delete operation 5 Times.But what if the array contains no 5th smallest element say

our array contain [1,1,1,1,1,1,1,1,1,1]

now in this case we need to do extract min operation n number of times which would give nlogn time?

Plz Clear my doubt

in Algorithms 288 views

5th Smallest element in a heap is relative to the smallest element, hence in this case should return 1 i.e., the extract min should run 5 times and should return 1. But if u talk about the fifth smallest distinct element then implementing it through minheap is surely taking O(nlogn) for the array u mentioned. Instead u can first use one loop to check how many distinct numbers are there in an array which would take O(n) (by using concept similar to that in counting sort) and if there are less numbers, you can conclude that there is no distinct 5th smallest element. If more elements then u can continue with extract min.

I didn't get your question exactly. what do you want to ask?

To extract k-smallest element the time complexity is O(klogn), why?

I have considered the min-heap was already built[which takes O(n) time].
swap the root with the last node and fix the heap of heapsize-1(as we do not consider the last node to participate in heap fix), this will give next smallest element on root.
Similarly, repeat this process 2 time if you want 2nd minimum element and k-time if you want kth smallest element.
Each min-heap fix will take O(lgn) time and there are 'k' such min-heap fixes as we do min-heapfix after every min-extract.
I got sir but now i have a doubt which case to consider if question simply ask to find 7th smallest element now how to interpret it 7th distinct smallest element or simply 7th Smallest element.

Cuz for distinct it can be O(nlogn) and in Normal its O(logn)

Cuz for distinct it can be O(nlogn) and in Normal its O(logn)

 Can you show me how it is O(lgn)?

We can be given two Case:-

1. Using only standard heap operation :-

The reason is same as You commented above only the thing is O(klogn) = O(logn) cuz if we are finding 7th smallest element k = 7 which is O(7logn) = O(logn)

2. If Only traversal we have to do then its O(1) ?

1st smallest = will be at first level so 1 comparision

2st smallest = will be at level 1 or level 2 total 3 elements total comaparision in between 2^2 - 1 = 3

Likewise 7th element will be upto 7th Level so total number of comparisons = 2^7 - 1 =127

So O(1)

Please log in or register to answer this question.

Related questions

6 votes
3 answers
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 ?
asked Sep 4, 2016 in Algorithms Kapil 2.1k views
9 votes
6 answers
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)$
asked Dec 28, 2014 in Algorithms Vikrant Singh 1.4k views
0 votes
0 answers
In a binary min heap with n elements, the 7th smallest element can be found in _____ ? Answer given is O(logn) and solution:- Delete the 1st smallest element O(logn) Delete the 2nd smallest element O(logn) .... Delete the 7th smallest element O(logn). ... O(logn). In this solution the data arrangement of the heap will be changed after performing these operation. any better solution than this???
asked Oct 18, 2017 in Programming Shubhanshu 705 views
1 vote
1 answer
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?
asked Dec 1, 2018 in Algorithms gmrishikumar 641 views