Heaps binarios y colas de prioridad

Árbol binario completo dentro de un array: cada padre le gana a sus hijos. Agarra siempre el extremo — la cola de prioridad.

Orden débil, una garantía fuerte

• Padre ≤ hijos (min-heap) — nada sobre los hermanos
• El mínimo siempre es la raíz → peek O(1)
• Los hijos de i en 2i+1, 2i+2 — sin punteros (array como árbol)
• push: sift up · pop: sift down — O(log n)

Mira el push (arriba) y el pop (abajo)

Push de 1 → sube hasta la raíz. Pop → la última hoja a la raíz, y baja. Nunca está totalmente ordenado — nomás padre < hijos.

Costos

peek O(1) · push/pop O(log n) · construir O(n). heapq ≈13× más rápido (C).

Solo el extremo es rápido

• Encontrar/eliminar un valor arbitrario: O(n)
• heapq es un MIN-heap — niega para máximo; haz push de tuplas (priority, item)
• No hay decrease-key → borrado perezoso (el truco de Dijkstra)

Para llevar

Mínimo esfuerzo para responder una sola pregunta: ¿cuál es el extremo? El motor de Dijkstra, Prim, Huffman y los schedulers. Sigue: tries.