7th smallest element in a Min-Heap

Question

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 ?

Comments

In the question what do we mean by term "distinct" ?

---

duplicates are not allowed, What will be the answer if we were asked to find the

1. $\\ (n-7)^{th} \\ $ smallest element
2. $\\ \frac{n}{7}^{th}\\$ smallest element

 

---

1. $\Theta (1)$
2. $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

Answer 1

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)

Comments

ok fine...so to find kth smallest element from the min heap..we can do in O(1) time.

---

yes..

---

Here you are taking 7 as a Constant. What if it's nth smallest?  Will it be n * log n??

Answer 2

It will take O(1)

    

Comments

I think same here

but for 1st one, answer is given O(lg N).

Answer 3

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