🧱 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.

85713958137AntesDespués de insertar 9El 9 se añade al final y sube: intercambia con 7 y con 8

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ónArreglo
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ónEfectoCosto
push(x)insertar xO(log n)
top()consultar el extremo sin retirarloO(1)
pop()retirar el extremo, sin devolverloO(log n)
empty() / size()comprobar si está vacía / contar elementosO(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.

Más práctica en 11 - Colas de prioridad.