Heaps

Question

In a min heap time complexity for

1: Find the 7^th smallest element

2: Delete the 7^th smallest element

Comments

@Rishav, with that idea, it would mean 1,1 doesn't have a second smallest number. Second smallest is also the greatest number in this case. Which would mean there's no greatest number. Which certainly is there. So 1 is the 1st as well as second smallest number.

---

 Vikas Verma if question would have asked 7th distinct smallest then , i think it would be O(n)

---

Yes @Rishav in case of duplicate elements also 7th smallest will be O(1).bt in case of distinct 7th smallest then it would have been O(n) i think because we will have to check for duplicates and that may lead us upto the last index.

Answer 1

 

1. in min heap, we know that 7th minimum will be present maximum till 7th level, and there will 127 elements till 7th level, so we have to do only constant time comparison, and it will take O(1) time.

NOTE: if elements are repeated then also finding 7th smallest will be O(1) .

consider this, 1,1,1,1,1,2,2,3,3,3,4,4,4,4,4,,5,5,5,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9 

 its True because

1₁,1₂,1₃,1₄,1₅,2₆,2₇,3,3,3,4,4,4,4,4,,5,5,5,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9 

Though duplicates are there but we define k^th min element as the element that comes at kth index after sorting the elements of heap. That also will be present at most at the 7th level only.  

Here 7th smallest element is 2 only. 

$\Rightarrow$  if question would have asked 7th distinct smallest then , i think it would be O(n)

2. O(1) for finding 7th smallest + O(1) for deleting it + O(log n) for applying min heapify = O(log n)

Note: I recommend to read the above top 15 comments.