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 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.