Heap Smallest Element

Question

My question is in Question like find 5th Smallest element in a heap:

It requires O(logn) time if we do only Delete operation 5 Times.But what if the array contains no 5th smallest element say

our array contain [1,1,1,1,1,1,1,1,1,1]

now in this case we need to do extract min operation n number of times which would give nlogn time?

Plz Clear my doubt

https://gateoverflow.in/1110/gate2003-23

Comments

I got sir but now i have a doubt which case to consider if question simply ask to find 7th smallest element now how to interpret it 7th distinct smallest element or simply 7th Smallest element.

Cuz for distinct it can be O(nlogn) and in Normal its O(logn)

---

Cuz for distinct it can be O(nlogn) and in Normal its O(logn)

 Can you show me how it is O(lgn)?

---

We can be given two Case:-

1. Using only standard heap operation :-

The reason is same as You commented above only the thing is O(klogn) = O(logn) cuz if we are finding 7th smallest element k = 7 which is O(7logn) = O(logn)

2. If Only traversal we have to do then its O(1) ?

1st smallest = will be at first level so 1 comparision

2st smallest = will be at level 1 or level 2 total 3 elements total comaparision in between 2^2 - 1 = 3

Likewise 7th element will be upto 7th Level so total number of comparisons = 2^7 - 1 =127

So O(1)