37 views
How to delete the last node in a max-heap or min-heap?

Do we delete it directly or like in normal case- replace it with itself then call max heapify on it and then finally decrease heap size?
| 37 views

### If you are implementing a generalized delete function for any given index:

You will have to delete like in normal case –

1. Replace the element to be deleted by the last element

2. Decrease the size by 1

3. Call heapify() for that index

We know that this works in $O(LogN)$ time.

But specifically for the last element, when we call $\text{heapify(last_index), last_index}$ will be out of range of the heap’s size, as we have already decreased the heap’s size before calling $\text{heapify()}$, hence $\text{heapify()}$ will simply return without any modification in the heap. Hence, this will have same effect as decreasing the size without calling $\text{heapify()}$. So, this will work in $O(1)$ for last element.

So, if you specifically want to implement the deletion of last node, then you can just decrease the size without calling $\text{heapify()}$.

Both implementations will work in $O(1)$ for the last element.

by (855 points)
selected ago by
0
thank you :-)