Deleting an item from the heap

The delete operation is another primary operation on a heap and is used to delete a given node (identified by its index in the array) 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 directly delete a non-leaf node, since removing one would leave a hole in the middle of the complete binary tree and break its structure. To overcome this, we swap the value at the given node with the last node in the binary tree (the rightmost node on the deepest level). Since the last node is a leaf node, we can easily delete it without breaking the complete binary tree.

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 of the two children is greater than the parent, we swap them (the current node with the larger child) 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.