El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Montículos (Heaps)

Siguiente ►
►

Hora de saldar la deuda más antigua del curso. En el módulo 4, la BandejaUrgencias de TaskFlow despachaba siempre la tarea más prioritaria usando heapq como caja negra: metíamos tuplas (prioridad, contador, tarea) y salían en orden, "por arte de magia y en O(log n)", con la promesa de abrir la caja en este módulo. Ya tienes todas las piezas: sabes qué es un árbol binario completo (06-02), conoces la representación en array con índices 2i+1/2i+2 (06-02) y entiendes por qué las operaciones O(altura) son rápidas si la altura es logarítmica. El montículo (heap) combina las tres ideas con una relajación genial: no mantiene el orden total del ABB — solo garantiza que cada padre es menor o igual que sus hijos — y con ese contrato mínimo consigue insertar y extraer el mínimo en O(log n) sobre un simple array, sin nodos ni referencias. En esta lección implementarás el montículo completo, reconstruirás la BandejaUrgencias sobre él y cerrarás la tabla comparativa de las colas de prioridad.

Contenido

  1. La propiedad de montículo: orden parcial, no total
  2. La forma: árbol completo = array sin huecos
  3. Insertar: flotar (sift-up)
  4. Extraer el mínimo: hundir (sift-down)
  5. La clase Monticulo completa
  6. BandejaUrgencias 2.0: la caja negra, abierta
  7. Bonus: heapify en O(n), heapsort y el max-heap

La propiedad de montículo: orden parcial, no total

Un min-heap es un árbol binario que cumple dos condiciones:

  • Propiedad de forma: es un árbol binario completo (todos los niveles llenos salvo el último, rellenado de izquierda a derecha — 06-02).
  • Propiedad de montículo: todo padre es menor o igual que cada uno de sus hijos.

Y nada más. Compáralo con el ABB, porque el contraste es la clave de la lección:

graph TD
    subgraph "Min-heap válido"
        A((1)) --> B((3))
        A --> C((2))
        B --> D((7))
        B --> E((4))
        C --> F((5))
        C --> G((9))
    end
ABB (06-04) Min-heap
Regla izquierda < nodo < derecha padre ≤ hijos (sin distinguir lados)
Tipo de orden total: el inorden lo lista todo ordenado parcial: solo garantiza el camino raíz-hoja
¿Dónde está el mínimo? hoja más a la izquierda (O(altura)) la raíz, siempre (O(1))
¿Buscar un valor cualquiera? O(altura) O(n) — no hay pistas de dónde está
¿Rangos, sucesor, listado ordenado? sí no
Forma la que salga (por eso existe el AVL) completa por definición: altura ⌊log₂ n⌋ gratis

Mira el diagrama: el 3 está a la izquierda del 2 y a nadie le importa — entre hermanos no hay ningún orden. Un heap es un ABB que ha renunciado a casi todo: no sabe listar ordenado, ni responder rangos, ni encontrar un elemento. A cambio de esa renuncia, gana dos cosas que el ABB no tiene: el mínimo en la raíz siempre, y equilibrio perfecto por definición (la forma completa no es negociable, así que no hay degeneración posible ni falta un AVL que la vigile). Es la especialización perfecta para una única pregunta: "¿cuál es el más urgente?" — exactamente la pregunta de una cola de prioridad. Regla mental para elegir: ¿necesitas todos los elementos en orden en cualquier momento? ABB/AVL. ¿Solo el siguiente más pequeño, una y otra vez? Heap.

La forma: árbol completo = array sin huecos

Aquí germina la semilla plantada en 06-02: como el heap es siempre un árbol completo, vive perfecto en un array sin desperdiciar una casilla — nada de NodoBinario, ni referencias, ni memoria extra. El diagrama anterior es, en memoria, esto:

monticulo = [1, 3, 2, 7, 4, 5, 9]
#  índices:  0  1  2  3  4  5  6

Con la aritmética de 06-02 como única navegación: hijos de i en 2i+1 y 2i+2, padre en (i-1)//2. Verifica la propiedad sobre el array: monticulo[1] = 3 ≥ monticulo[0] = 1 (padre en (1-1)//2 = 0), monticulo[5] = 5 ≥ monticulo[2] = 2... La propiedad de montículo, traducida a array: arr[i] >= arr[(i-1)//2] para todo i > 0.

Cuando en el módulo 4 escribimos heapq.heappush(bandeja, ...) sobre una lista de Python y te pedimos fe: esto es lo que había. heapq no es una estructura: son funciones que mantienen esta propiedad sobre una lista normal. Imprime un heap de heapq y verás el array de arriba — desordenado a simple vista, ordenado según el contrato del heap.

Insertar: flotar (sift-up)

Para insertar hay que conservar las dos propiedades. La estrategia: garantizar la forma primero y reparar el orden después.

  1. Coloca el elemento nuevo en la única posición que mantiene el árbol completo: el final del array (el primer hueco del último nivel).
  2. Puede que ahora sea menor que su padre, violando la propiedad. Se corrige haciéndolo flotar (sift-up): mientras sea menor que su padre, intercámbialos y sube.

Insertemos el 0 en el heap del ejemplo, con traza completa:

[1, 3, 2, 7, 4, 5, 9, 0]      0 entra en i=7; su padre: (7-1)//2 = 3, vale 7
        0 < 7: intercambio  →  [1, 3, 2, 0, 4, 5, 9, 7]   ahora i=3, padre i=1 (vale 3)
        0 < 3: intercambio  →  [1, 0, 2, 3, 4, 5, 9, 7]   ahora i=1, padre i=0 (vale 1)
        0 < 1: intercambio  →  [0, 1, 2, 3, 4, 5, 9, 7]   i=0: es la raíz, fin
graph TD
    subgraph "1. El 0 entra al final"
        A((1)) --> B((3))
        A --> C((2))
        B --> D((7))
        B --> E((4))
        C --> F((5))
        C --> G((9))
        D --> H((0))
    end
    subgraph "2. Tras flotar hasta la raíz"
        A2((0)) --> B2((1))
        A2 --> C2((2))
        B2 --> D2((3))
        B2 --> E2((4))
        C2 --> F2((5))
        C2 --> G2((9))
        D2 --> H2((7))
    end

Fíjate en lo que el 0 no tocó: el subárbol del 2 ni se enteró. Flotar solo recorre el camino del nuevo nodo hacia la raíz — como mucho la altura del árbol, que en un árbol completo es ⌊log₂ n⌋ clavados. Inserción: O(log n), garantizado sin rotaciones ni vigilantes.

Extraer el mínimo: hundir (sift-down)

El mínimo es la raíz (arr[0]), pero arrancarla dejaría un agujero arriba — y los arrays odian los agujeros en el índice 0 (¿recuerdas el desencolar O(n) de la cola sobre lista, en el módulo 4?). El truco espejo del anterior — forma primero, orden después:

  1. Guarda la raíz (es el resultado). Mueve el último elemento del array a la raíz — la forma vuelve a ser correcta, encogida por donde toca.
  2. Ese elemento probablemente es demasiado grande para la cima: húndelo (sift-down) — mientras sea mayor que alguno de sus hijos, intercámbialo con el menor de los dos y baja.

Extraigamos del heap resultante [0, 1, 2, 3, 4, 5, 9, 7]:

sale el 0; el último (7) sube a la raíz  →  [7, 1, 2, 3, 4, 5, 9]
   hijos del 7 (i=0): 1 (i=1) y 2 (i=2); el menor es 1
   7 > 1: intercambio                    →  [1, 7, 2, 3, 4, 5, 9]
   hijos del 7 (i=1): 3 (i=3) y 4 (i=4); el menor es 3
   7 > 3: intercambio                    →  [1, 3, 2, 7, 4, 5, 9]
   hijos del 7 (i=3): solo 7... no tiene (2·3+1 = 7 ≥ len): es hoja, fin

¿Por qué con el menor de los dos hijos? Porque el elegido se convertirá en padre del otro: si subiéramos el mayor, violaríamos la propiedad en el acto. Es el error clásico de implementación — con dos hijos 3 y 4, subir el 4 deja 4 > 3 como padre de 3.

Coste: de nuevo el camino de la raíz a una hoja como máximo — O(log n). Y la secuencia de extracciones sucesivas devuelve los elementos en orden ascendente: 0, 1, 2, 3... cada extracción reorganiza lo justo para que el nuevo mínimo aflore a la cima.

La clase Monticulo completa

Todo junto, en una clase con la interfaz de una cola de prioridad:

class Monticulo:
    """Min-heap sobre una lista de Python. Los elementos deben ser comparables."""

    def __init__(self):
        self.datos = []

    def __len__(self):
        return len(self.datos)

    def ver_minimo(self):
        """El mínimo sin extraerlo. O(1): es la raíz."""
        return self.datos[0] if self.datos else None

    def insertar(self, elemento):
        """Añadir al final y flotar. O(log n)."""
        self.datos.append(elemento)
        self._flotar(len(self.datos) - 1)

    def extraer_minimo(self):
        """Sacar la raíz, subir el último y hundirlo. O(log n)."""
        if not self.datos:
            return None
        minimo = self.datos[0]
        ultimo = self.datos.pop()          # O(1): quitar por el final
        if self.datos:                     # si queda alguien, ocupa la cima y se hunde
            self.datos[0] = ultimo
            self._hundir(0)
        return minimo

    def _flotar(self, i):
        while i > 0:
            padre = (i - 1) // 2
            if self.datos[i] < self.datos[padre]:
                self.datos[i], self.datos[padre] = self.datos[padre], self.datos[i]
                i = padre                  # seguir subiendo desde la nueva posición
            else:
                break                      # el padre ya es menor o igual: en su sitio

    def _hundir(self, i):
        n = len(self.datos)
        while True:
            izq, der = 2 * i + 1, 2 * i + 2
            menor = i
            if izq < n and self.datos[izq] < self.datos[menor]:
                menor = izq
            if der < n and self.datos[der] < self.datos[menor]:
                menor = der                # el menor de los tres: padre, izq, der
            if menor == i:
                break                      # ya es menor que ambos hijos: en su sitio
            self.datos[i], self.datos[menor] = self.datos[menor], self.datos[i]
            i = menor                      # seguir bajando desde la nueva posición

Detalles que merecen segunda lectura:

  • _hundir calcula menor entre tres candidatos (el propio nodo y sus hijos existentes): así el intercambio es siempre con el menor de los hijos y las comprobaciones izq < n cubren los nodos con un solo hijo o ninguno.
  • En extraer_minimo, el caso "quedaba un solo elemento" sale gratis: pop() lo saca, self.datos queda vacío y no se hunde nada.
  • Probemos que la magia del módulo 4 ya no es magia:
m = Monticulo()
for x in [5, 3, 8, 1, 9, 2]:
    m.insertar(x)
print(m.datos)          # [1, 3, 2, 5, 9, 8] — el array-heap, a la vista
while len(m):
    print(m.extraer_minimo(), end=" ")   # 1 2 3 5 8 9 — ascendente

Esto es, línea por línea de comportamiento, lo que heapq.heappush y heapq.heappop hacían en el módulo 4 (con la lista expuesta en vez de encapsulada — decisión de diseño de Python, TDA vs implementación del módulo 1). Caja negra: abierta.

BandejaUrgencias 2.0: la caja negra, abierta

Reconstruyamos la BandejaUrgencias del módulo 4 sobre nuestro montículo, con su misma interfaz y su mismo truco de las tuplas (prioridad, contador, tarea) — que ahora entiendes del todo: las tuplas se comparan elemento a elemento, así que el heap ordena por prioridad; el contador de itertools.count desempata FIFO entre iguales y evita que la comparación llegue al dict (los diccionarios no se comparan con <; sin contador, dos tareas de igual prioridad reventarían con TypeError).

from itertools import count

class BandejaUrgencias:
    """Cola de prioridad de TaskFlow. Prioridad 1 = máxima.
    Misma interfaz que en el módulo 4; motor propio."""

    def __init__(self):
        self._heap = Monticulo()
        self._contador = count()           # desempate FIFO y escudo anti-TypeError

    def llega(self, tarea):
        self._heap.insertar((tarea["prioridad"], next(self._contador), tarea))

    def siguiente(self):
        """La tarea más urgente (y más antigua entre iguales), o None."""
        entrada = self._heap.extraer_minimo()
        return entrada[2] if entrada else None

    def urgente_a_la_vista(self):
        entrada = self._heap.ver_minimo()
        return entrada[2] if entrada else None

bandeja = BandejaUrgencias()
bandeja.llega({"id": "T-11", "titulo": "Informe semanal", "prioridad": 3, "estado": "pendiente"})
bandeja.llega({"id": "T-12", "titulo": "Servidor caido", "prioridad": 1, "estado": "pendiente"})
bandeja.llega({"id": "T-13", "titulo": "Revisar PR", "prioridad": 2, "estado": "pendiente"})
bandeja.llega({"id": "T-14", "titulo": "Base de datos lenta", "prioridad": 1, "estado": "pendiente"})

print(bandeja.siguiente()["id"])   # T-12  (prioridad 1, llegó antes que T-14)
print(bandeja.siguiente()["id"])   # T-14  (prioridad 1)
print(bandeja.siguiente()["id"])   # T-13  (prioridad 2)

Y la tabla que el módulo 4 dejó a medias, ahora completa — las tres implementaciones de cola de prioridad, cara a cara:

Implementación (módulo) llega (insertar) siguiente (extraer mín.) urgente_a_la_vista
ColaPrioridadNoOrdenada (4) O(1) O(n) — buscar el mínimo O(n)
ColaPrioridadOrdenada (4) O(n) — insertar_ordenado O(1) O(1)
Montículo (6) O(log n) O(log n) O(1)

Las dos primeras pagaban O(n) en una de las dos operaciones — mantenían demasiado poco orden (ninguno) o demasiado (total). El heap es el equilibrio exacto: el orden justo para responder "¿el siguiente?" rápido, ni una gota más. Con 10 000 tareas y tráfico constante de llegadas y despachos, es la diferencia entre miles de operaciones por evento y ~13. Esta idea — pagar solo por el orden que de verdad consumes — es de las más rentables que te llevas del curso.

Bonus: heapify en O(n), heapsort y el max-heap

Heapify. ¿Convertir una lista de n elementos en heap? Insertarlos uno a uno cuesta O(n log n). Pero hay un camino mejor, y en 06-02 (ejercicio 2) viste la pieza clave: en un array-heap, todos los índices desde n//2 hasta el final son hojas — y una hoja ya es un mini-heap válido. Basta entonces recorrer los nodos internos de atrás hacia delante (n//2 - 1 → 0) hundiendo cada uno: cuando le toca a un nodo, sus dos subárboles ya son heaps, y hundirlo funde los tres en uno. La cuenta sorprende: la mitad de los nodos (hojas) trabajan 0, un cuarto hunde 1 nivel, un octavo 2... la suma converge a O(n), no O(n log n) — casi todos los nodos están abajo y tienen poco que hundir. Es lo que hace heapq.heapify, y por eso es la forma correcta de arrancar un heap desde datos existentes.

Heapsort. Heapify O(n) + extraer el mínimo n veces O(log n) = una lista ordenada en O(n log n) garantizado y sin memoria extra (la versión in-place usa un max-heap y va dejando cada máximo al final del propio array). Ahí queda la mención: los algoritmos de ordenación merecen su propio curso, pero ya sabes que uno de los tres grandes (con mergesort y quicksort) es este árbol disfrazado de array.

Max-heap. ¿Y si quisieras el máximo primero (tareas por horas estimadas, puntuaciones)? Opción purista: invertir las comparaciones de Monticulo (padre ≥ hijos). Opción pragmática — y el idioma estándar con heapq, que solo trae min-heap: negar la clave al insertar (insertar(-valor)) y negar al extraer. El mínimo de los negados es el máximo de los originales. Este truco reaparecerá en el ejercicio top-k de la próxima lección.

Errores Comunes y Consejos

  • Hundir intercambiando con el hijo equivocado. Siempre con el menor de los dos hijos; con el otro, la propiedad se rompe en el mismo intercambio. Es el bug número uno de los heaps caseros.
  • Olvidar que el heap no está ordenado. m.datos no es una lista ordenada, y recorrerla no da orden ascendente (mira [1, 3, 2, 5, 9, 8]). El orden solo emerge extrayendo. Si necesitas listar todo en orden repetidamente sin vaciar nada, tu estructura es el AVL, no el heap.
  • Buscar o borrar un elemento arbitrario en O(log n). El heap no indexa por valor: localizar "la tarea T-13" es O(n). Las variantes con mapa auxiliar (posición de cada elemento) existen — así hacen los planificadores reales el decrease-key — pero no salen gratis ni vienen en heapq.
  • Meter dicts (o cualquier no comparable) a pelo. insertar(tarea) con dos tareas de igual prioridad acaba comparando diccionarios: TypeError. La tupla (prioridad, contador, tarea) es el traje reglamentario; el contador, su cremallera.
  • Consejo: en producción usa heapq — es C compilado, está bien probado y ahora sabes exactamente qué hace por dentro (y por qué opera sobre una lista normal a la vista). El Monticulo propio es para aprender y para entrevistas, donde "implementa un heap" sigue siendo un clásico.

Ejercicios

Ejercicio 1: la traza sin ordenador

Sin ejecutar código: parte del heap [2, 5, 3, 9, 6, 8] y aplica (a) insertar(1) y después (b) extraer_minimo(). Escribe el array tras cada intercambio. Comprueba luego con la clase Monticulo.

Ejercicio 2: ¿es un heap válido?

Escribe es_min_heap(lista) que verifique en O(n) si una lista cumple la propiedad de min-heap, y úsala como auditor: genera 100 listas aleatorias, conviértelas en heap insertando elemento a elemento en un Monticulo, y comprueba que las 100 pasan la auditoría (y que la lista original casi nunca la pasa).

Ejercicio 3: fusionar bandejas

Dos equipos de TaskFlow fusionan sus bandejas de urgencias (dos Monticulo con m y n elementos). Escribe fusionar(m1, m2) que devuelva un Monticulo nuevo con todo. Compara el coste de (a) extraer todo de ambos e insertarlo en el nuevo, frente a (b) concatenar los arrays internos y "heapificar" hundiendo los internos de atrás hacia delante. Implementa la (b).

Soluciones

Solución 1

(a) insertar(1): el 1 entra en i=6 → [2, 5, 3, 9, 6, 8, 1]. Su padre es i=2 (vale 3): 1 < 3 → [2, 5, 1, 9, 6, 8, 3]. Nuevo padre i=0 (vale 2): 1 < 2 → [1, 5, 2, 9, 6, 8, 3]. Fin: dos intercambios, el 1 en la cima.

(b) extraer_minimo(): sale el 1; el último (3) sube → [3, 5, 2, 9, 6, 8]. Hijos del 3: 5 y 2, menor el 2: 3 > 2 → [2, 5, 3, 9, 6, 8]. Hijos del 3 (i=2): solo el 8 (i=5): 3 < 8, fin. Comentario: hemos vuelto exactamente al heap de partida — insertar y extraer el mínimo recién insertado deja el resto como estaba, señal de que ambas operaciones tocan solo el camino imprescindible.

Solución 2

import random

def es_min_heap(lista):
    for i in range(1, len(lista)):
        if lista[i] < lista[(i - 1) // 2]:     # ¿menor que su padre? violación
            return False
    return True

fallos = 0
for _ in range(100):
    original = [random.randint(0, 999) for _ in range(50)]
    m = Monticulo()
    for x in original:
        m.insertar(x)
    assert es_min_heap(m.datos)                # las 100 pasan
    fallos += not es_min_heap(original)
print(f"originales que no eran heap: {fallos}/100")   # ~100

Comentario: el auditor recorre cada nodo comprobándolo contra su padre — basta, porque la propiedad de heap es local (padre-hijo directo). Contrasta con el ABB, donde comprobar solo contra el padre era el error clásico: allí la propiedad habla de subárboles enteros. Mismo gesto, validez opuesta — entender por qué es entender la diferencia entre orden parcial y total. (Un heap de 50 valores aleatorios "de nacimiento" es rarísimo: de ahí el ~100.)

Solución 3

def fusionar(m1, m2):
    resultado = Monticulo()
    resultado.datos = m1.datos + m2.datos          # concatenar: la forma ya es válida
    for i in range(len(resultado.datos) // 2 - 1, -1, -1):
        resultado._hundir(i)                       # heapify: internos de atrás adelante
    return resultado

a, b = Monticulo(), Monticulo()
for x in [4, 9, 6]: a.insertar(x)
for x in [1, 7, 3]: b.insertar(x)
c = fusionar(a, b)
print([c.extraer_minimo() for _ in range(len(c))])   # [1, 3, 4, 6, 7, 9]

Comentario: la opción (a) — extraer e insertar todo — cuesta O((m+n)·log(m+n)); la (b) concatena en O(m+n) y heapifica en O(m+n): lineal total, gracias al argumento de la sección bonus (las hojas, más de la mitad, no trabajan). El bucle arranca en el último nodo interno (n//2 - 1, el padre del último elemento) y retrocede hasta la raíz: cuando _hundir(i) se ejecuta, los subárboles de i ya son heaps válidos — el mismo razonamiento "de hijos a padres" del postorden. Es literalmente heapq.heapify escrito a mano.

Conclusión

Promesa cumplida: la caja negra del módulo 4 está abierta y dentro había un árbol binario completo viviendo en un array — la semilla de 06-02 hecha estructura. Ya sabes su contrato (padre ≤ hijos: orden parcial, lo justo para tener el mínimo en la raíz, frente al orden total del ABB), sus dos gestos (flotar al insertar, hundir al extraer, ambos O(log n) por un camino raíz-hoja de altura garantizada), su arranque en frío (heapify O(n)), sus parientes (heapsort, max-heap por negación) y su lugar en TaskFlow: la BandejaUrgencias definitiva, que cierra la tabla de colas de prioridad ganando en la operación que las otras dos pagaban a O(n). Con esto, el arsenal del módulo está completo: árbol genérico para jerarquías, recorridos para explotarlas, ABB/AVL para orden y rangos, árbol B para el disco y heap para urgencias. La próxima lección no añade teoría: es el gimnasio — seis ejercicios progresivos donde todas estas piezas trabajan juntas sobre TaskFlow, incluidos los clásicos de entrevista (validar un ABB, reconstruir un árbol, top-k con montículo). A entrenar.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados