Arboles en montón; ordenación por montón.

Suponga que H es un árbol binario completo con N elementos. (al menos de que se indique lo contrario , asumiremos que H se tiene un memoria como un array lineal árbol mediante representación secuencial, no en representación enlazada).

Se dice que H es u árbol en montón, montón máx. si cada nodo de N de H tiene la siguiente propiedad: el valor de N es mayor o igual que el valor de cualquier hijo de N. (un montón min se define analógicamente: el valor de N es menor o igual que el valor de cualquier hijo de N).

Ejemplo 7.19

Considere el árbol completo H de la figura 7-29(a). Observe que H es un árbol en montón. Esto significa, en particular, que el mayor elemento de H aparece en lo <> del montón, o sea, en la raíz del árbol. La figura 7-19 (b) muestra la presentación secuencial de H en el array ARBOL [1] es la raíz d3el árbol H, y los hijos de izquierdo y derecho de un nodo ARBOL [K] son, respectivamente, ARBOL [2K] y árbol [2K+1]. Esto significa en particular, que el padre de cualquier nodo de raíz árbol [J] es el nodo ARBOL [J÷2] (donde J÷2 significa división entera). Observe que los nodos de H del mismo nivel aparecen uno tras otro en el array ARBOL.