The DELETE operation is based on `SIFT DOWN', which, as the name suggests, is the exact opposite of SIFT UP.
SIFT DOWN starts with a value in any node. It moves the value down the tree by successively exchanging the value with the smaller of its two children. The operation continues until the value reaches a position where it is less than both its children, or, failing that, until it reaches a leaf.
Example: sift down 29 in this tree:
Note: The tree's shape does not change. if it was a complete tree to start with, it will still be complete when the operation is done.
Complexity = O(height) = O(logN)