Deleting an item from the heap

The delete operation is another primary operation on a heap and is used to delete a given node (by address) from the tree. The implementation is encapsulated in the delete function, which deletes the given node in the binary tree and ensures the resulting tree still follows the max-heap property. Let us look at the algorithm and implementation of the delete operation on a max heap implemented as an array.

Algorithm

The algorithm for deleting a value in a heap is quite similar to insert. However, we cannot delete a non-leaf node, which would break the tree. To overcome this, we swap the value at the given node with the last node in the binary tree. Since the last node is a leaf node, we can easily delete it.

Swapping the value from the last node to the given node might violate the heap property in the resulting tree, so we need to recalibrate it to enforce the heap property. To do this, we traverse downwards from the given node (that now has the swapped value) and, at each iteration, compare the current node with its children. If the larger child is greater than the parent, we swap them and continue traversal in that direction. The traversal stops when we reach a leaf node, or the current node is larger than both its children.