Made Easy Test Series

Question

What is worst case time complexity to delete middle element from the min heap of n distinct elements?

1. O(logn)

2. O(n)

100. O(nlogn)

500. O($n^{2}$)

Comments

Thanks for that but if we have a very large n then  no if leaves will be of O(n/2) middle element will be closest to leaves i.e just above one level from leaves, so from there we have to move to root so it takes O(logn  - 1) was my thought.

---

We must move down i.e. push-down from the deleted index to the leaf.

We move up i.e. push-up when a new element is added to the heap.

---

@Arjun sir please help to explain??

Answer 1

The leaves of the heap forms the mojority of elements , it can be the case that middle element is present at the leaf and there are n/2 leaves .so finding an element from n/2 takes O(n). Now delete the element whitakes constant time O(1). We have to Reheapify now to arrange the heap which will take O(logn). So total O(n)+O(logn)= O(n) should be the answer

Answer 2

Find Middle element (i.e mid index) of the array at n/2 -----> O(1)

Delete Mid and replace it with last element -------> O(1)

Build heap ----> O(n) or you can use heapify bottom-up approach O(logn)

Dominant term- > O(logn)