Condition (2) tells us which node must disappear: we must take away the rightmost node in the bottom level. This node must be `deleted' even if it is not the node containing V!
Example: delete 15 (the root) from this tree:
So we end up with a value (30) that has no node, and a node (`15') that has no value. The algorithm, then, is obvious.
Example: Delete 15 - delete the bottom right node, put its value (30) in the node where 15 was. 30 is smaller than 20 so we sift 30 down, with the final result:
Example: Delete 50 from this tree - delete the bottom right node, put its value (37) in the node where 50 was. 37 is smaller than 38 so we sift 37 UP, with the final result:
A special case of the DELETE operation is GET_SMALLEST, which returns the smallest value in a given heap and deletes the value from the heap.
How do you find the smallest value in a heap?
Answer: It is always in the root.