Awesome q2a theme
0 votes
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?
in Algorithms by (27 points) | 37 views

1 Answer

+7 votes
Best answer

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 :-)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,446 questions
2,720 answers
13,274 comments
95,468 users