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 ? DS data-structures binary-heap time-complexity + – Kapil asked Sep 4, 2016 recategorized Jul 6, 2022 by Lakshman Bhaiya Kapil 3.9k views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments Nandkishor3939 commented Jan 15, 2019 reply Follow Share In the question what do we mean by term "distinct" ? 0 votes 0 votes shashank023 commented Oct 10, 2020 reply Follow Share duplicates are not allowed, What will be the answer if we were asked to find the $\\ (n-7)^{th} \\ $ smallest element $\\ \frac{n}{7}^{th}\\$ smallest element 0 votes 0 votes Shiva Sagar Rao commented Apr 11, 2021 reply Follow Share $\Theta (1)$ $O(n)$ If elements are repeated, then also this holds true. Consider the heap array 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 The given procedure returns 1 and that is the correct answer. “7" must be returned only if the questions asks "7th" distinct smallest element which might require entire scanning of the heap and needs a hashtable to be run in $O(n)$ time Source: Arjun sir comment 0 votes 0 votes Please log in or register to add a comment.
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) prasitamukherjee answered Sep 5, 2016 prasitamukherjee comment Share Follow See all 7 Comments See all 7 7 Comments reply Kapil commented Sep 5, 2016 reply Follow Share check this => http://stackoverflow.com/questions/7650917/oklogk-time-algorithm-to-find-kth-smallest-element-from-a-binary-heap 0 votes 0 votes prasitamukherjee commented Sep 5, 2016 reply Follow Share good algorithm!! i wasn't aware of such a solution. thanks!! 0 votes 0 votes cse23 commented Oct 13, 2016 reply Follow Share @kapilp are you sure for first one it is O(logn) If we will go with simple procedure like 1+2+3+....2^n-1 comaprison to find nth smallest element then it is O(1) another one is start deleting the element till kth level to reach the kth smallest element which is O(logn) because everywhere I am seeing O(1) as well O(logn) time...can u plz confirm?? even I am bit confuse see this: https://gateoverflow.in/5915/complexity-finding-smallest-element-already-constructed http://stackoverflow.com/questions/21600312/searching-the-7th-largest-element-in-a-max-heap 0 votes 0 votes Kapil commented Oct 14, 2016 reply Follow Share @cse23, yes, it is O(1). and for 2nd it is O(N). 0 votes 0 votes cse23 commented Oct 14, 2016 reply Follow Share ok fine...so to find kth smallest element from the min heap..we can do in O(1) time. 0 votes 0 votes Kapil commented Oct 14, 2016 reply Follow Share yes.. 0 votes 0 votes anonymous commented Oct 4, 2017 reply Follow Share Here you are taking 7 as a Constant. What if it's nth smallest? Will it be n * log n?? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes It will take O(1) Rakеsh Kumar answered Sep 4, 2016 Rakеsh Kumar comment Share Follow See 1 comment See all 1 1 comment reply Kapil commented Sep 4, 2016 reply Follow Share I think same here but for 1st one, answer is given O(lg N). 0 votes 0 votes Please log in or register to add a comment.
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 saicharan answered Jul 17, 2019 saicharan comment Share Follow See all 0 reply Please log in or register to add a comment.