CODEWITHSUNDEEP
algorithmtreeheapbinary-tree
eyesima
eyesima

Reputation: 235

How do you delete the last node in a (min-) heap?

I'm learning for an exam and currently I'm at heaps. I have understood how to delete a node from a heap but I could find a case where I cannot use the algorithm to delete.

The problem is I want delete 15 which is a leaf and the last node of the min heap. When you delete a node in a heap, you are looking for the last node of the heap, replace it with the deletion node and check if the children of this node are greater than it.. then continue this recursively.

For this reason (15 is last element and has no children), I don't know how to delete it. 

        1
     /     \
    9       6
   / \     /
 17  11   8
 /
15

I would think that you can just delete it without doing anything else. You basically replace it by itself since the deletion node = last node..? So it looks like that:

        1
     /     \
    9       6
   / \     /
 17  11   8

I hope you can help me, I really need to know that for my exam and I couldn't find anything about that case on the internet.

Upvotes: 0

Views: 1499

Answers (1)

MBo
MBo

Reputation: 80187

Removing last node is very simple task - just remove it, nothing to do more (except for decrementing counter and resizing array if needed). In general function swapping item with itself change nothing (while useless work is done), but you can check whether item is the last and omit swap.

Note that removing non-head element is rare problem (you have to provide explicit access to it), most algorithms use only the topmost element.

Note also that your picture does not show valid binary heap, because heap is complete binary tree, and all levels (except for the last) must be filled completely, but your tree has empty place in the third row.

Upvotes: 2

Related Questions