Montículos y colas de prioridad

Una cola de prioridad es un tipo de dato abstracto que siempre produce el elemento de mayor (o menor) prioridad; los montículos son las estructuras estándar basadas en árboles que lo implementan con operaciones eficientes de inserción y extracción del mínimo.

Definition

Una cola de prioridad es un tipo de dato abstracto que soporta la inserción de elementos con prioridades y la extracción del elemento de mayor prioridad; un montículo es una estructura de datos basada en árboles que satisface la propiedad de montículo —la clave de cada nodo se ordena consistentemente en relación con sus hijos— que implementa una cola de prioridad de manera eficiente.

Scope

Este tema cubre el tipo de dato abstracto (ADT) de cola de prioridad y sus implementaciones de montículo: el montículo binario y su representación en array, la propiedad de montículo y las operaciones de "sift-up"/"sift-down", el algoritmo Heapsort, y montículos fusionables avanzados como los montículos binomiales y de Fibonacci que mejoran los costos de disminución de clave y unión. Se conecta con algoritmos de grafos (Dijkstra, Prim) y simulación basada en eventos, que dependen de las colas de prioridad.

Core questions

• ¿Qué operaciones definen el ADT de cola de prioridad y cómo las implementa un montículo?
• ¿Cómo permite la propiedad de montículo encontrar el mínimo en tiempo constante e insertar/extraer en tiempo logarítmico?
• ¿Cómo se almacena un montículo binario de forma compacta en un array y cómo se construye en tiempo lineal?
• ¿Cómo utiliza Heapsort un montículo para ordenar in situ en tiempo O(n log n)?
• ¿Cuándo mejoran los montículos fusionables, como los montículos de Fibonacci, los algoritmos que disminuyen las claves con frecuencia?

Key concepts

• ADT de cola de prioridad
• propiedad de montículo
• montículo binario
• representación de montículo basada en array
• sift-up y sift-down
• construcción de montículo en tiempo lineal
• Heapsort
• montículos de Fibonacci y binomiales

Key theories

Propiedad de montículo y representación en array

Un montículo binario es un árbol binario casi completo en el que la clave de cada nodo domina las de sus hijos; se puede almacenar en un array con indexación implícita padre-hijo, lo que permite insertar y extraer en O(log n) y encontrar el mínimo en O(1).

Eficiencia amortizada de los montículos de Fibonacci

Los montículos de Fibonacci soportan la disminución de clave en tiempo amortizado O(1) y la extracción del mínimo en tiempo amortizado O(log n), mejorando el tiempo de ejecución asintótico de algoritmos como los de Dijkstra y Prim que realizan muchas disminuciones de clave.

Clinical relevance

Las colas de prioridad son una infraestructura esencial: ordenan tareas listas en los planificadores de sistemas operativos, gestionan eventos en la simulación de eventos discretos, impulsan la búsqueda "best-first" y A*, y proporcionan la frontera en los algoritmos de Dijkstra y Prim. Heapsort ofrece una ordenación in situ de O(n log n) con límites garantizados en el peor de los casos.

History

J. W. J. Williams introdujo el montículo binario y Heapsort en 1964, y Robert Floyd presentó el procedimiento de construcción de montículo en tiempo lineal poco después. Los montículos binomiales (Vuillemin, 1978) y los montículos de Fibonacci (Fredman y Tarjan, 1987) añadieron una fusión eficiente y una disminución de clave amortizada, lo que mejoró los tiempos de ejecución de los algoritmos clásicos de grafos.

Key figures

• J. W. J. Williams
• Robert W. Floyd
• Michael Fredman
• Robert Tarjan

Seminal works

• williams1964
• fredman1987
• cormen2009

Frequently asked questions

¿Por qué almacenar un montículo binario en un array en lugar de usar punteros?

Un montículo binario es un árbol binario casi completo, por lo que sus nodos se asignan limpiamente a índices de array consecutivos: un nodo en el índice i tiene hijos en 2i y 2i+1. Esto evita la sobrecarga de punteros, mejora el comportamiento de la caché y simplifica la navegación aritmética.

¿Cuándo justifican los montículos de Fibonacci su complejidad?

Los montículos de Fibonacci ofrecen una disminución de clave amortizada de O(1), lo que mejora el tiempo de ejecución asintótico de algoritmos como los de caminos más cortos de Dijkstra en grafos densos. En la práctica, sus grandes factores constantes suelen significar que los montículos binarios más simples son a menudo más rápidos, por lo que son relevantes principalmente para límites teóricos y casos especializados.