The delete operation is based on sift down.

Sift Down: move a value down the tree by exchanging it with the smaller of its 2 children. Sift 29 down this tree:

To delete V from a heap:

1. V must not be in the resulting heap.
2. The resulting heap must be a complete tree.

Condition (2) forces us to remove the rightmost node in the bottom level, even if this is not the node containing V!

Delete 15 from: