Eliminación de la raíz de un montón

Suponga que H es un montón con N elementos y suponga que queremos eliminar la raíz R de H. esto se lleva acabo como sigue:

(1)  Asignar la raíz R a alguna variable ITEM.

(2)  Reemplazar el nodo R a eliminar con el último nodo L de H de forma que H sigue siendo completo, aunque no necesariamente un montón.

(3)  (Re amontonar.) hacer que L se mueva a su sitio adecuado en H para que H sea finalmente un montón.

Procedimiento 7.11: ELIMONTON (ARBOL, N, ITEM)              Un árbol en memoria H con N elementos se tiene en el array ARBOL, este            procedimiento asigna        La raíz ARBOL [1]  de H a la variable  ITEM y entonces  reamontona los restantes elementos. La       Variable ULT guarda el valor del último nodo original de H. los punteros PTR, IZQ y DER dan las         Posiciones de ULT y de sus hijos izquierdo y derecho a medida que ULT se mueve por el árbol. Hacer ITEM:=ARBOL [1]. [eliminar la raíz de H]. Hacer ULT:=ARBOL [N] Y N:=N-1. [quitar el último nodo de H]. Hacer PTR:=1, IZQ:=2 y DER:=3. [inicializar punteros], Repetir pasos 5 a 7 mientras DER≤N:      Si ULT≥ARBOL [IZQ] y ULT≥ARBOL [DER], entonces: hacer ARBOL [PTR]:=ULT y volver.     [Fin de condicional]. Si ÁRBOL [DER]≤ARBOL [IZQ], entonces:       Hacer ARBOL [PTR]:=ARBOL [IZQ] y PTR:=IZQ Y PTR:=IZQ Si no: Hacer ARBOL [PTR]:=ARBOL [DER] y PTR:=DER. [Fin de condicional]. Hacer IZQ :=2*PTR y DER:=IZQ+1. [Fin del bucle del paso 4]. Si IZQ=N y si ULT PTR:=IZQ. Hacer ARBOL [PTR]:=ULT Volver.