Complexity

Question

In the max heap where the smallest element reside

i)if all element are distinct?

ii) if all element are not distinct?

What is the time complexity in both the cases?

If any space complexity required ?

Comments

i)if all element are distinct? ...

Ans- Smallest element must be among the leaf nodes of max -heap.

Time complexity - O(n)... Just search last n/2 elements of max heap array.

---

1) if all are distinct, then search all leaves in O(n) time

2) If all are equal, then searching leaf takes O(1) time

---

I think there is a difference between ii) if all element are not distinct and your 2nd statement " If all are equal". 

Am i right ??

---

yes , there is a difference .it means some can be same and some can be different .

so i think we can augment our heap by providing ranking to all the elements and then the heap will become distinct 

and then as it will be same as all are distinct so , it will also be O(n)

what do u say?