GUÍA 23-09-26 Estructuras de Datos

CN122 · miércoles 23/09/2026 · 13:00-14:15 · Sesión 13

Colas de prioridad

EL CONCEPTO

En una cola de prioridad no sale el que llegó primero sino el más urgente. Cada elemento lleva una prioridad y el desencolado extrae el de mayor prioridad; los empates se resuelven por orden de llegada.

IMPLEMENTACIONES POSIBLES

• Arreglo desordenado — insertar O(1), extraer O(n) porque hay que buscar el máximo.
• Arreglo ordenado — insertar O(n) por el corrimiento, extraer O(1).
• Montículo (heap) — insertar y extraer en O(log n). Es el equilibrio correcto.

EL MONTÍCULO BINARIO

Árbol binario completo donde todo padre tiene prioridad mayor o igual que sus hijos. Se guarda en un arreglo sin apuntadores, aprovechando la aritmética de índices.

• Hijos de i: 2i+1 y 2i+2. Padre de i: (i−1)/2.
• Insertar: colocar al final y flotar hacia arriba mientras sea mayor que su padre.
• Extraer: tomar la raíz, poner el último en la raíz y hundirlo mientras algún hijo sea mayor.

POR QUÉ O(LOG N)

Un árbol binario completo con n nodos tiene altura ⌊log₂n⌋. Flotar y hundir recorren a lo sumo un camino de la raíz a una hoja, y por eso el costo es logarítmico.

APLICACIONES

• Planificación de procesos por prioridad.
• Algoritmo de Dijkstra para caminos mínimos.
• Compresión de Huffman.
• Heapsort, que ordena en O(n log n) sin memoria adicional.

PRÁCTICA

Implementar la cola de prioridad con arreglo ordenado y con montículo, y comparar tiempos con 10⁵ elementos.