Content deleted Content added
Reverted 1 edit by 189.121.105.99 (talk): Previous version is correct. |
Tag: Reverted |
||
Line 56:
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 root, you swap elements. Insert the remaining element to a child subtree. Picking the child controls balance, using any of the common balance mechanisms.
.
I find a height (AVL) balance is the simplest 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 has height 0, so a leaf is height 1. You insert to one side, say left, unless the right height is less. When you pop, pop from left first for equal keys, as it is more heavily populated.
.
Heaps generally do not support a stable sort unless you either add the order as a min secondary key, or push all later equal keys right (temporarily increasing imbalance) and pop equal key elements always left first (or vice versa).
.
=== Extract===
| |||