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 vijaycs commented Sep 4, 2016 reply Follow Share O(n) for both. 1 votes 1 votes Kapil commented Sep 4, 2016 reply Follow Share For 2nd one , O(n) is right, as we have to use hashtable . For 1st, O(lgn) is given . I think it should be O(1) . 0 votes 0 votes vijaycs commented Sep 4, 2016 reply Follow Share Ohh ... yes ... if we have elements like - 1,2 ,3,3,4,4,5,5,5,6,6,6,7 And ans for 1st is 5 and for 2nd it is 7 then you are correct... 1 votes 1 votes srestha commented Sep 4, 2016 reply Follow Share 1) O(1), because we can do it in constant time 2) O(N) counting sort will be applied 2 votes 2 votes Habibkhan commented Oct 14, 2016 reply Follow Share I agree the operation concerned is find() , which takes O(1) if duplicates are allowed but if asked for distinct 7th minimum and duplicates are allowed we may need to do find() operation for entire tree which will take O(n) time 0 votes 0 votes hungrysoul554 commented Dec 30, 2017 reply Follow Share @srestha how can you apply counting sort on this bcoz he mentioned heap right ? 0 votes 0 votes 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 Show 4 previous comments 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.