madeeasy

Question

I think it is loglogn

Comments

But number of comparison will be loglogn

because as heap is balanced tree , it has height of logn

now to find appropriate place for root element , we have to travel maximum height of logn , and we can do binary search on this logn elements. hence effectively loglogn

---

ok fine i understood , we can not perform binary search on logn elements , because  we don't know which path will root element follow. hence we don't know elements on which we can perform binary search

---

So in this case a deletion in min heap or max heap should also take loglogn ?

You have a valid point on number of comparisons , but time complexity depends too on number of swaps and at each level in worst case 1 swap happens so in log n height logn swaps occur.

And time complexity always takes the higher order terms.

Answer 1

it will take O(nlogn)  where n is no of node  and logn is height of tree