Binary heap: Difference between revisions

Revision as of 20:34, 7 September 2023

Revision as of 20:39, 7 September 2023

Line 58:

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.

.

I find a heightHeight (AVL) balance control is thea simplestsimple 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).

.

=== Extract===