#Binary Max Heap Question (Doubt)

Question

Let's say we're given with a MAX Heap and we want to delete any of the leaf node, then how much time will it take to delete any of the leaf node and maintain the max heap property?

My main doubt is - will it O(n) time to reach to leaf nodes?

Comments

To find that particular leaf element O(n)

To maintain heap property O(log n)

Total O(n)

---

@ Tesla! Thanks buddy! and thank you srestha Ma'am.

---

we want to delete any of the leaf node

$O(1)$ will suffice for deleting any leaf node(If you are asked to delete any leaf node and not some specific leaf node)...Just delete the last element. 

Answer 1

Heap is nothing but an array with heap property. So If you wish to delete just $any$ leaf node, then Just delete the last element of the Heap and it will take just $O(1)$ time since It is an array and you can go to the last element in $O(1)$ time.

Comments

previous of last node , is also a leaf node

Wouldn't be true if $n=2$ 

---

then also $O(1)$ if $n=2$

if $n>2$ then too $O(1)$

---

There are approx n2 leaves in the Heap. So, If we wish to delete some Specific leaf node then first we would have to find it, which could take O(n) time itself. Then after finding that leaf we can delete that node in just logn time. 

 

So, it's O(n) * O (logn) = O(n), right?