Inserción en un árbol en montón

Suponga que H es un montón con N elementos y suponga que se da un ITEM de información insertamos ITEM en el montón H tal y como sigue:

(1)  Primero se añade ITEM al final de H, de forma que H sigue siendo un árbol completo aunque no necesariamente  un montón.

(2)  Entonces se subir a ITEM hasta su <> en H para que H sea finalmente un montón

La forma en que funciona este procedimiento se ilustra a continuación antes de presentarlo formalmente.

Ejemplo 7-20

Considere el montón H de la figura 7-29. Suponga que queremos añadir ITEM=70 a H. primero ajuntamos 70 como el siguiente elemento del árbol completo, esto es, hacemos ARBOL [21]=70. Entonces 70 es el hijo derecho del ÁRBOL [10]=48. En la figura 7-30(a) esta dibujado el camino desde la raíz de H hasta 70. Ahora buscamos el sitio adecuado para 70 en el montón como sigue:

(a) Comparamos 70 con su padre, 48. Como 70 es mayor que 48, intercambiamos 70 y 48; el camino ahora aparece como en la figura 7-30(b).

(b)  Comparamos 70 con su nuevo padre 55. Como 70 es mayor que 55, intercambiamos; el camino ahora aparece como en la figura 7-30(c).

(c)  Comparamos 70 con su nuevo padre, 88. Como 70 no excede a 88, ITEM=70 ha llegado a su lugar adecuado en H.