Ponerlo al final del array (el árbol sigue completo).
Subir: mientras x sea menor que su padre, intercambiarlos.
Solo el camino de x hacia la raíz puede romper el invariante, así que solo se revisa ese camino: como mucho la altura, O(log n) intercambios.
Un ejemplo: el heap [3, 6, 5, 9, 8], al que se añade 4. Cada dibujo muestra el árbol (arriba) y el array (abajo).
Paso 1 de 3. Se añade 4 al final (posición 5). Su padre es la posición (5 − 1) / 2 = 2, que vale 5. 4 es menor que 5: se intercambian.Paso 2 de 3. Tras el intercambio, 4 está en la posición 2 y 5 en la posición 5.Paso 3 de 3. 4 se compara con su nuevo padre, 3. 4 no es menor que 3: no hay intercambio y subir termina.
Borde grueso: lo que se compara. Relleno con asterisco: lo que acaba de cambiar.
Texto
función subir(a, i): mientras i > 0 y a[i] < a[(i − 1) / 2]: intercambiar a[i] y a[(i − 1) / 2] i ← (i − 1) / 2