Montículos y colas de prioridad: saber siempre qué toca después

← Volver a Blog y artículos

Una cola de prioridad responde rápido a una pregunta: ¿cuál es el elemento más urgente ahora mismo? Un montículo es la estructura estándar que la implementa.

Forma y regla

Un montículo binario es un árbol binario completo almacenado en un arreglo. En un montículo de mínimos, cada padre es menor o igual que sus hijos, de modo que el elemento más pequeño está en la raíz. Para el nodo con índice i, los hijos están en 2*i* + 1 y 2*i* + 2, y el padre en (i − 1) // 2. No se necesitan punteros.

Dos operaciones hacen el trabajo

Para insertar, se coloca el nuevo elemento al final y se hace subir mientras sea menor que su padre. Para extraer el mínimo, se toma la raíz, se mueve el último elemento a su lugar y se hace bajar intercambiándolo con su hijo menor hasta que se restablezca la regla. Cada operación recorre como máximo la altura del árbol, así que ambas son O(log n). Consultar el mínimo es O(1).

Dónde aparecen los montículos

El algoritmo de Dijkstra y A* usan una cola de prioridad para elegir el siguiente nodo.
Los planificadores la emplean para ejecutar primero la tarea de mayor prioridad.
Los problemas de «los k mayores» mantienen un montículo de tamaño k.
El ordenamiento por montículo ordena en O(n log n).

Un montículo no es una lista ordenada

Un montículo solo garantiza que la raíz es el mínimo. El resto del arreglo está ordenado solo de forma parcial. Para leer todos los elementos en orden hay que extraerlos uno a uno. Construir un montículo a partir de n elementos existentes es posible en O(n).

Un truco práctico

Para hallar los k valores mayores de un flujo de datos, mantén un montículo de mínimos de tamaño k. Cuando llegue un valor mayor que el menor del montículo, sustitúyelo. El montículo siempre contiene los k mejores vistos hasta el momento.

Continúa con el libro

Consulta el tratamiento completo, los ejemplos y los ejercicios en Algoritmos explicados con claridad.