CODEWITHSUNDEEP
heap
Robo Jumble
Robo Jumble

Reputation: 5

Remove an Element from a heap

My initial approach to implement this method would be to replace the desired element with the last element of the heap and then heapify like you would for removing the root,however this wouldn’t be correct as the last element may not be a child node of the element that is to be removed and the heap structure will be broken.

So how do I go about making sure I am maintaining the heap structure?

Upvotes: 0

Views: 480

Answers (1)

trincot
trincot

Reputation: 350212

replace the desired element with the last element of the heap

Yes, this is the way to go.

and then heapify like you would for removing the root, however this wouldn’t be correct as the last element may not be a child node of the element that is to be removed and the heap structure will be broken.

That concern can be resolved by first checking if the moved value has to bubble up or down, and to apply the appropriate bubble algorithm (up or down).

Upvotes: 1

Related Questions