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

nlogn +O(1) =O(nlogn)??

first sort them nlogn then find middle...

---

if you know the position then, just swap the element to be deleted by right most leaf and then call min_heapify on the index of the swapped element(deleted) $O(\log n)$

---

if you don't know the position of the element to be deleted  in the heap,then it will be $O(n)$ for selecting the element and then min_heapify it in $O(\log n)$ so overall $O(n)$

---

O(logn), middle element can be found in O(1), replace with last element and then call min-heapify.

---

YA WE CAN KNOW THE POSITION IN O(1) TYM BECZ OF ARRAY SO ONLY logn is required.

---

According to me it should be a constant time operation.

Finding mid element in a heap: O(1)

Replacing mid element by last element: O(1)

Since middle element resides in the second last level of heap, thus Heapify: O(1)

---

@Pratik Gawali i agree to your point. it should be o(1) as you explained.

---

@Pratik Gawali after moving mid element to last and deleting we have to rehepify so that it should be a heap . We need O(logn) for this

---

O(logn) operation is needed when root is deleted as there are logn levels below root. But in this case there is only one level below mid element, so O(1).

---

Ok but how can you know the middle element will be @ middle of array. By saying middle element they mean the middle element of the sorted array right??

---

I believe they mean middle element of the heap i.e element at $(n/2)^{th}$ index of array as the answer given by them is O(logn).

If they would have meant middle element of the sorted array then answer must have been O(nlogn) as sorting would have been the most expensive step.

---

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)