Reinventarlo

¿Por qué el hijo menor?

Al bajar, el elemento se intercambia con el menor de sus dos hijos. Alguien propone intercambiar siempre con el hijo izquierdo, «por simplicidad».

Un nodo con valor 9 baja desde la raíz y sus hijos son 7 (izquierdo) y 4 (derecho). Si se intercambia siempre con el hijo izquierdo, «por simplicidad», ¿qué pasa?El 7 sube y queda como padre del 4, que es menor: el invariante se rompeQueda bien, y el 9 baja otro nivel hasta ser una hoja, con algún paso de másSe rompe la forma del árbol: queda un nivel incompletoQueda bien: 7 y 4 son hermanos, y el invariante no compara hermanos