which is a valid max-heap. There is no need to check the left child after this final step: at the start, the max-heap was valid, meaning the root was already greater than its left child, so replacing the root with an even greater value will maintain the property that each node is greater than its children ({{nowrap|11 > 5}}; if {{nowrap|15 > 11}}, and {{nowrap|11 > 5}}, then {{nowrap|15 > 5}}, because of the [[transitive relation]]).
An alternative to leaf insertion that supports balance is to insert root to leaf recursively. For a max heap, if your element's key is greater than that of the current root, you swap elements. Insert the remaining element to a child subtree. Picking the child controls balance, using any of the common balance mechanisms.
Height (AVL) balance control is a simple mechanism, and very fast. As you return from each insert to a subtree, you set the height of this node to 1 + max height (right, left). A no child subtree (null reference or pointer) has height 0, so a leaf is height 1. You insert to one side, say left, unless the right height is less. (When you extract, extract from left first for equal keys, as it is probably more heavily populated. This is the only control extract has on tree balance.)
Heaps generally do not support a stable sort unless you either add the order as a min secondary key, or insert all later equal keys right (temporarily increasing imbalance) and extract equal key elements always left first (or vice versa).
