Montículos

En ocasiones nos interesa tener algunos datos acomodados de modo que siempre sea fácil acceder al dato más grande (o alternativamente, al más pequeño). Esto se podría lograr si mantuvieramos a todos los datos completamente ordenados (como en una lista ordenada o en un árbol binario ordenado) pero en realidad esto no es necesario. A continuación mostraremos una estructura de datos (llamada montículo) basada en un árbol binario que cumple este propósito.

Definición de un montículo

Decimos que un árbol binario satisface la condición de montículo si cada padre es mayor que sus hijos. A diferencia de los árboles binarios ordenados, no hay ninguna condición que relacione a los hijos de un mismo padre (ni mucho menos a los de padres distintos). Finalmente, diremos que un árbol binario es un montículo si satisface la condición de montículo y, además, es un árbol binario completo, es decir, todos los niveles del árbol (excepto tal vez el último) están repletos, y en el último nivel todos los hijos están acumulados del mismo lado (digamos a la izquierda).

Así, de los siguientes árboles binarios, el primero no satisface la condición de montículo, el segundo no es completo y el tercero sí es un montículo.

Representación de montículos

Como los montículos son árboles binarios completos, una forma conveniente de representar un montículo es mediante un arreglo.

Como los arreglos en C (y en C++, etc.) comienzan en la posición 0, podemos poner allí a la raíz del árbol, luego a sus hijos en las posiciones 1 y 2, a los hijos de 1 en las posiciones 3 y 4, a los hijos de 2 en las posiciones 5 y 6, etc. La regla es, por supuesto, poner a los hijos de K en las posiciones 2K+1 y 2K+2. Observe que esto nos simplifica la tarea de averiguar dónde están los hijos de un padre. Averiguar dónde está el padre de un hijo no es más dificil: el padre de K está en la posición (K-1)/2.

En Pascal a veces es conveniente declarar los arreglos como comenzando en la posición 1, y podemos poner allí a la raíz del árbol, luego a sus hijos en las posiciones 2 y 3, a los hijos de 2 en las posiciones 4 y 5, a los hijos de 3 en las posiciones 6 y 7, etc. La regla es, por supuesto, poner a los hijos de K en las posiciones 2K y 2K+1. Observe que esto nos simplifica la tarea de averiguar dónde están los hijos de un padre. Averiguar dónde está el padre de un hijo no es más dificil: el padre de K está en la posición K div 2.

De cualquiera de estas formas, el montículo de la figura estará representado por el arreglo P M O L I.

Operaciones sobre montículos

Las dos operaciones principales que nos interesan son las de crear un montículo a partir de un vector cualquiera y la de eliminar a la raíz de un montículo sin perder la estructura. A continuación mostramos como crear un montículo a partir del vector O L I M P:

A cada paso, insertamos un nuevo elemento al final del montículo (indicado con verde). En los primeros tres pasos (al insertar la O, la L y la I) no ocurre nada especial, pues cada hijo resulta menor que su padre. Al insertar la M en el cuarto paso, notamos que esto ya no es cierto, y tenemos que arreglar el montículo. Esto consiste en intercambiar el nuevo elemento con su padre mientras éste último sea mayor. En otras palabras, el nuevo elemento sube en el montículo (indicado con rojo) y sus padres bajan en el montículo (indicado con azul) mientras los padres sean menores. En nuestro caso, la M sólo subió una posición, pues es menor a la O. Finalmente, al insertar la P en el quinto paso, notamos que ésta debe subir dos niveles, en donde se convierte en la nueva raíz del montículo. En términos del vector que representa al montículo, después de cada uno de los pasos éste se ve así: (1) O L I M P, (2) O L I M P, (3) O L I M P, (4) O M I L P y (5) P O I L M.

¿Cuántas operaciones se harían en el peor de los casos para crear un montículo con N elementos? Observe que al insertar el K-ésimo elemento, éste puede subir un máximo de log₂ K niveles. Así, el número máximo de veces que tendríamos que intercambiar dos elementos al construir un montículo es log₂ 1 + log₂ 2 + ... + log₂ N que es menor a N log₂ N.

Ahora destruyamos el montículo, eliminando a cada paso a la raíz del montículo:

A cada paso, eliminamos la raíz del montículo y, como esa posición no debe quedar vacía, la reemplazamos por el último elemento del montículo (indicado con verde). Normalmente, el árbol que queda no es un montículo y hay que arreglarlo nuevamente. En nuestro primer paso, al poner a M como raíz se viola la condición de montículo, pues M no es mayor que O. El arreglo consiste en intercambiar a M con uno de sus hijos. ¿Cuál de los dos? Si la intercambiaramos con I, entonces no habríamos arreglado nada, pues I no es mayor que O ni mayor que M. Luego, lo que tenemos que hacer es intercambiar a M con el mayor de sus hijos, en nuestro caso, con O. En otras palabras, a cada paso la nueva raíz va bajando (indicado con azul) y el mayor de sus hijos va subiendo (indicado con rojo) hasta que la nueva raíz no sea menor que ninguno de sus hijos. En el segundo paso eliminamos a la O, colocamos a L como nueva raíz y notamos que para arreglar el montículo debemos intercambiarla con la M. En el tercer paso eliminamos a la M, colocamos a la I como nueva raíz y notamos que hay que intercambiarla con la L. En el cuarto paso eliminamos a la L y colocamos a la I como nueva raíz.

Si en lugar de eliminar la raíz, simplemente la intercambiamos con el último elemento del montículo y luego la ignoramos, entonces, en términos del vector que representa al montículo, después de cada uno de los pasos éste se ve así: (1) O M I L P, (2) M L I O P, (3) L I M O P y (4) I L M O P. Observemos que el último vector está ordenado ascendentemente.

¿Cuántas operaciones se harían en el peor de los casos para destruir un montículo con N elementos? Observe que al eliminar la K-ésima raíz, la nueva raíz puede bajar un máximo de log₂ (N-K-1) niveles. Así, el número máximo de veces que tendríamos que intercambiar dos elementos al destruir un montículo es log₂ (N-1) + log₂ (N-2) + ... + log₂ 2 que es menor a N log₂ N.

Ordenamiento de montículo

Si comenzamos con un vector de tamaño N, luego creamos un montículo y luego lo destruimos, obtenemos un vector ordenado. A este algoritmo de ordenamiento se le conoce como ordenamiento de montículo. Del análisis expuesto arriba, se ve que el tiempo de ejecución de este algoritmo es de O(N log N) en el peor de los casos, es decir, tan rápido como se podría esperar de un algoritmo de ordenamiento basado en comparaciones.

© 2004 Francisco Javier Zaragoza Martínez
Creado el 11 de Agosto de 2004
Última modificación el 12 de Agosto de 2004