🧱 priority_queue (heap)
Estructura de datos · Viene en la librería estándar (STL) · Tema: Estructuras de Datos Catálogo completo: Catálogo de estructuras
📍 Dónde se aprende: módulo 11 de la Ruta de Aprendizaje.
El problema: atender siempre la tarea más urgente
Llegan tareas con prioridades numéricas. Queremos insertar una tarea, consultar la más urgente y retirarla. Buscar el máximo recorriendo todas las tareas cuesta O(n) cada vez; mantener todo ordenado puede hacer costosas las inserciones.
Una cola de prioridad mantiene disponible el elemento extremo. La implementación habitual es un heap binario: un árbol casi completo donde cada padre tiene prioridad mayor o igual que sus hijos. Así el mayor está siempre en la raíz. Solo necesitas conocer arreglos para entender cómo se representa.
Orden parcial: suficiente para encontrar el máximo
Considera el arreglo [8,5,7,1,3]. Representa este árbol colocando los hijos
del índice i en 2i+1 y 2i+2. El padre de i > 0 está en (i−1)/2,
con división entera. Los niveles se llenan de izquierda a derecha.
Si el diagrama no cabe, deslízalo horizontalmente.
Cada padre domina a sus hijos, pero los hermanos no tienen que estar ordenados: 5 está antes que 7 en el arreglo. No podrías hacer búsqueda binaria sobre él. La propiedad basta para que ningún descendiente supere a la raíz.
Insertar y extraer
Insertamos 9 al final, para mantener la forma del árbol:
| Paso de inserción | Arreglo |
|---|---|
| Añadir 9 como hijo de 7 | [8,5,7,1,3,9] |
| 9 supera a su padre 7: intercambiar | [8,5,9,1,3,7] |
| 9 supera a su padre 8: intercambiar | [9,5,8,1,3,7] |
Solo pueden estar mal las relaciones del camino hacia la raíz. Al subir el elemento hasta que su padre lo domine, restauramos la propiedad del heap.
Para extraer ese 9 ponemos el último elemento, 7, en la raíz y quitamos la
última casilla: [7,5,8,1,3]. Comparamos con el mayor de los hijos y
lo intercambiamos con 8: queda [8,5,7,1,3]. Bajar por el hijo mayor evita
dejar al otro hijo por encima de su nuevo padre.
La altura es O(log n): insertar sube por un camino y extraer baja por otro. Leer la raíz cuesta O(1); almacenar n elementos cuesta O(n).
Usar priority_queue en C++
La biblioteca mantiene esos intercambios por nosotros. Este programa usa otro ejemplo pequeño para mostrar tanto el máximo como el mínimo:
#include <bits/stdc++.h>
using namespace std;
int main() {
priority_queue<int> maxheap; // el mayor arriba
priority_queue<int, vector<int>, greater<int>> minheap; // el menor arriba
maxheap.push(5); maxheap.push(1); maxheap.push(8);
minheap.push(5); minheap.push(1); minheap.push(8);
cout << maxheap.top() << " " << minheap.top() << "\n"; // 8 1
maxheap.pop(); // ahora el mayor es 5
priority_queue<pair<int,int>> tareas; // de pares: compara por .first
tareas.push({3, 100}); // (prioridad, id)
tareas.push({7, 200});
cout << tareas.top().second << "\n"; // 200: la de prioridad 7
}
Imprime primero 8 1 y después 200. priority_queue<int> deja arriba
el mayor; la versión con greater<int> deja arriba el menor, invirtiendo
la comparación entre padres e hijos.
| Operación | Efecto | Costo |
|---|---|---|
push(x) | insertar x | O(log n) |
top() | consultar el extremo sin retirarlo | O(1) |
pop() | retirar el extremo, sin devolverlo | O(log n) |
empty() / size() | comprobar si está vacía / contar elementos | O(1) |
Para obtener y quitar un elemento, guarda primero top() y luego llama a
pop(). Ambas operaciones requieren que la cola no esté vacía.
Se admiten prioridades repetidas. Los pares se comparan primero por .first
y, en caso de empate, por .second: no se conserva automáticamente el orden de llegada.
Cuándo elegirla
Úsala cuando intercalas inserciones y extracciones del extremo: tareas urgentes, los k mejores valores o distancias tentativas en Dijkstra. Si quieres recorrer todo ordenado una sola vez, ordenar un vector suele ser más simple.
priority_queue no ofrece buscar un elemento arbitrario, cambiar su prioridad
en su sitio ni borrarlo por identificador. Según el problema puedes usar
set y multiset o insertar una versión nueva y descartar las obsoletas
cuando lleguen arriba, como hace Dijkstra.
¿Por qué no intercambiamos siempre con el hijo izquierdo al extraer?
Con raíz 7 e hijos 5 y 8, el problema está a la derecha. Dejar 8 bajo 7 viola la propiedad. Debemos comparar ambos hijos y elegir el mayor.
Más práctica en 11 - Colas de prioridad.