Heapsort en Python — el puente entre arrays y árboles (con animación)

Heapsort es el algoritmo de ordenación que te garantiza O(n log n) siempre sin pedirte memoria extra. Es la solución cuando no quieres ni el peor caso de quicksort (O(n²)) ni la memoria O(n) de merge sort. Y es además la red de seguridad que muchos lenguajes modernos usan dentro de Introsort: si quicksort se atasca, pasan a heapsort.

Pero heapsort tiene algo único: es el primer algoritmo de la familia que usa una estructura de datos no trivial — el heap, que es un árbol binario completo metido en un array. Si lo entiendes, has dado el salto conceptual de “manipulo posiciones” a “manipulo una estructura”. Por eso heapsort es el puente natural entre los algoritmos sobre arrays y los algoritmos sobre árboles.

Esta entrada cubre el algoritmo en serio: cómo funciona paso a paso, cómo el heap se mapea a un array, implementación en Python, JavaScript y Java, su complejidad real, comparativa con sus rivales, y por qué los lenguajes lo usan como fallback.

Si quieres el panorama de los 14 algoritmos del clúster: Algoritmos de ordenación en Python — los 14 explicados.

Heapsort en una frase

Mete los elementos en un max-heap (árbol donde cada padre es mayor que sus hijos, así que el máximo siempre está en la raíz). Saca el máximo a la última posición; reduce el tamaño del heap en uno y re-heapifica. Repite. Cuando no queda nada, la lista está ordenada.

Animación sobre 12 valores:

Antes de seguir: qué quieren decir O, Θ y Ω

En las tablas de complejidad vas a ver tres símbolos. Idea rápida:

• O(n log n) — “O grande”, cota superior (peor caso). “Como mucho, n·log n operaciones.”
• Ω(n log n) — “Omega”, cota inferior (mejor caso). “Como mínimo, n·log n. Heapsort no puede ir más rápido.”
• Θ(n log n) — “Theta”: cuando superior e inferior coinciden, caso típico.

Heapsort es Θ(n log n) literal: mejor caso y peor caso son del mismo orden. Otro algoritmo Θ-constante, sin sorpresas según la entrada. Explicación más larga en el pilar del clúster.

La idea clave: un árbol metido en un array

Antes de entender heapsort tienes que entender el max-heap. Es un árbol binario que cumple dos propiedades:

1. Completo: se llena por niveles, de izquierda a derecha. Sin huecos.
2. Propiedad de heap: cada padre es mayor o igual que sus hijos.

         15            ← raíz, máximo de todos
        /  
      11    14
     /     / 
    10   8 12  6
   /
  5

Esto se almacena en un array sin punteros:

índice: 0  1  2  3  4  5  6  7
valor:  15 11 14 10 8  12 6  5

Para un nodo en el índice i:
– Hijo izquierdo = 2i + 1
– Hijo derecho = 2i + 2
– Padre = (i - 1) // 2

El nodo 15 (índice 0) tiene hijos en 1 (11) y 2 (14). El nodo 8 (índice 4) tiene padre en (4-1)//2 = 1 → 11. Funciona.

Esa idea — una estructura de árbol guardada como array sin punteros — es la primera vez que ves “manipular una estructura abstracta sobre una memoria plana”. Es el mismo truco que se usa en bases de datos para los índices y en JSON Trees, B-trees, etc. Heapsort es el algoritmo que te obliga a entenderlo bien.

Cómo funciona — traza paso a paso

Ordenamos [3, 1, 4, 1, 5] a mano.

Fase 1: construir el max-heap.

Partimos del array tal cual y “heapificamos desde el medio hacia atrás” (los nodos hoja ya están heapificados por sí solos).

inicio:       [3, 1, 4, 1, 5]
              ↑ índices 0..4

heapify(2):   nodo 4 (índice 2), sin hijos → ya bien.
heapify(1):   nodo 1 (índice 1), hijos: 1 (i=3), 5 (i=4).
              ¿1 < 5? Sí → intercambia → [3, 5, 4, 1, 1]
heapify(0):   nodo 3 (índice 0), hijos: 5 (i=1), 4 (i=2).
              ¿3 < 5? Sí → intercambia → [5, 3, 4, 1, 1]
              ahora heapify(1) recursivo: nodo 3, hijos 1, 1.
              3 ya es el mayor → para.

Heap construido: [5, 3, 4, 1, 1].

Fase 2: extraer máximos.

extrae(4):   intercambia raíz (5) con índice 4 → [1, 3, 4, 1, 5]
             reduce heap a tamaño 4. heapify(0):
             nodo 1, hijos 3 y 4. ¿1 < 4? Sí → swap con i=2 → [4, 3, 1, 1, 5]
             nodo 1 en i=2, sin hijos → para.

extrae(3):   intercambia raíz (4) con índice 3 → [1, 3, 1, 4, 5]
             heap tamaño 3. heapify(0):
             nodo 1, hijos 3 y 1. swap con i=1 → [3, 1, 1, 4, 5]
             nodo 1 en i=1, sin hijos → para.

extrae(2):   intercambia raíz (3) con índice 2 → [1, 1, 3, 4, 5]
             heap tamaño 2. heapify(0):
             nodo 1, hijo 1. iguales → para.

extrae(1):   intercambia raíz (1) con índice 1 → [1, 1, 3, 4, 5]
             heap tamaño 1. fin.

Resultado: [1, 1, 3, 4, 5]. Ordenado.

Implementación en Python

def ordenar(lista: list[int]) -> list[int]:
    n = len(lista)
    # 1) Construir el max-heap (de abajo arriba).
    for i in range(n // 2 - 1, -1, -1):
        _heapify(lista, n, i)
    # 2) Sacar el máximo al final, reducir el heap, repetir.
    for i in range(n - 1, 0, -1):
        lista[0], lista[i] = lista[i], lista[0]
        _heapify(lista, i, 0)
    return lista


def _heapify(lista: list[int], size: int, i: int) -> None:
    mayor = i
    izq = 2 * i + 1
    der = 2 * i + 2
    if izq < size and lista[izq] > lista[mayor]:
        mayor = izq
    if der < size and lista[der] > lista[mayor]:
        mayor = der
    if mayor != i:
        lista[i], lista[mayor] = lista[mayor], lista[i]
        _heapify(lista, size, mayor)


if __name__ == "__main__":
    print(ordenar([3, 1, 4, 1, 5]))  # [1, 1, 3, 4, 5]

Detalles:

1. In-place absoluto. El heap vive en la misma lista. Memoria extra: O(log n) por el stack de recursión, o O(1) si haces heapify iterativo.
2. _heapify se llama de abajo arriba en la construcción (range(n//2 - 1, -1, -1)). Los nodos hoja no necesitan heapify (no tienen hijos).
3. El “fin del heap” se mueve hacia la izquierda en la fase 2. Cada iteración sacamos el máximo a la posición correcta final y reducimos el heap activo.

En entrevistas, una pregunta clásica: ¿por qué la construcción es O(n) y no O(n log n)? Respuesta: porque el coste de heapificar nodos cerca de las hojas es bajo (poca profundidad) y la mayoría de los nodos están cerca de las hojas. La suma converge a O(n). Es contraintuitivo pero importante.

Implementación en JavaScript

function ordenar(lista) {
  const n = lista.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(lista, n, i);
  }
  for (let i = n - 1; i > 0; i--) {
    [lista[0], lista[i]] = [lista[i], lista[0]];
    heapify(lista, i, 0);
  }
  return lista;
}

function heapify(lista, size, i) {
  let mayor = i;
  const izq = 2 * i + 1;
  const der = 2 * i + 2;
  if (izq < size && lista[izq] > lista[mayor]) mayor = izq;
  if (der < size && lista[der] > lista[mayor]) mayor = der;
  if (mayor !== i) {
    [lista[i], lista[mayor]] = [lista[mayor], lista[i]];
    heapify(lista, size, mayor);
  }
}

console.log(ordenar([3, 1, 4, 1, 5])); // [1, 1, 3, 4, 5]

Implementación en Java

public static void ordenar(int[] lista) {
    int n = lista.length;
    for (int i = n / 2 - 1; i >= 0; i--) heapify(lista, n, i);
    for (int i = n - 1; i > 0; i--) {
        int tmp = lista[0]; lista[0] = lista[i]; lista[i] = tmp;
        heapify(lista, i, 0);
    }
}

private static void heapify(int[] lista, int size, int i) {
    int mayor = i, izq = 2 * i + 1, der = 2 * i + 2;
    if (izq < size && lista[izq] > lista[mayor]) mayor = izq;
    if (der < size && lista[der] > lista[mayor]) mayor = der;
    if (mayor != i) {
        int tmp = lista[i]; lista[i] = lista[mayor]; lista[mayor] = tmp;
        heapify(lista, size, mayor);
    }
}

Complejidad — la garantía sin memoria

Métrica	Mejor caso	Caso medio	Peor caso
Tiempo	Ω(n log n)	Θ(n log n)	O(n log n)
Memoria	O(1)	O(1)	O(1)
Estable	No	No	No

Como merge sort, los tres casos coinciden en Θ(n log n). A diferencia de merge, heapsort lo hace sin memoria extra. Esa es su superpotencia.

Demostración rápida:
– Construcción del heap: O(n) (no O(n log n), por la matemática del array no balanceado).
– Cada extracción: O(log n) (el heapify desciende como mucho log n niveles).
– N extracciones: n × O(log n) = O(n log n).

Por qué NO es estable. El intercambio entre la raíz y el último elemento del heap puede saltar elementos iguales. Si te importa la estabilidad, usa merge.

Ver en acción — heapsort sobre 10 listas fijas

Todo el clúster usa las mismas 10 listas fijas (n=15) para que la comparativa cruzada sea justa:

#	Nombre	Qué es
1	ordenada	1, 2, 3, ..., 15
2	inversa	15, 14, ..., 1
3	casi_ordenada	1..15 con un par de swaps
4	muy_desordenada	Patrón min-max alternado
5	duplicados	Enteros del rango [1..5] repetidos
6-10	aleatoria_s1 .. aleatoria_s5	5 permutaciones aleatorias deterministas

Aplicamos heapsort sobre las 10:

from sortlab import bench_estandar, formato_tabla
print(formato_tabla(bench_estandar("heap", n=15)))

Salida real (n=15):

Lista            Comp.  Interc.  Escr.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -------  -----  -----------  -----  -----------
ordenada         77          52    104        0.015  Único   Θ(n log n)
inversa          66          39     78        0.011  Único   Θ(n log n)
casi_ordenada    75          51    102        0.014  Único   Θ(n log n)
muy_desordenada  73          45     90        0.012  Único   Θ(n log n)
duplicados       66          35     70        0.011  Único   Θ(n log n)
aleatoria_s1     68          44     88        0.012  Único   Θ(n log n)
aleatoria_s2     75          48     96        0.013  Único   Θ(n log n)
aleatoria_s3     75          48     96        0.013  Único   Θ(n log n)
aleatoria_s4     73          47     94        0.013  Único   Θ(n log n)
aleatoria_s5     73          44     88        0.013  Único   Θ(n log n)

Lectura de la tabla:

• Comparaciones entre 66 y 77 — un rango estrechísimo. Heap es Único (no depende de la forma de la entrada), su sello.
• Θ observada = Θ(n log n) en todas las filas, sin oscilación. Cuando el clasificador detecta un algoritmo cuya complejidad NO depende de la entrada (heap es uno: siempre construye el heap y siempre extrae elemento a elemento), devuelve directamente su Θ teórica — no se deja engañar por los pocos elementos de n=15. La confirmación numérica con n=50 viene a continuación, por si quieres verlo crecer.

Confirmación con n=50

Para ver claro que heap es Θ(n log n) (y no Θ(n²)), repetimos con n=50:

print(formato_tabla(bench_estandar("heap", n=50)))

Lista            Comp.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -----------  -----  -----------
ordenada         434          0.070  Único   Θ(n log n)
inversa          379          0.056  Único   Θ(n log n)
casi_ordenada    428          0.068  Único   Θ(n log n)
muy_desordenada  407          0.061  Único   Θ(n log n)
duplicados       426          0.061  Único   Θ(n log n)
aleatoria_s1     410          0.060  Único   Θ(n log n)
aleatoria_s2     412          0.061  Único   Θ(n log n)
aleatoria_s3     407          0.060  Único   Θ(n log n)
aleatoria_s4     410          0.060  Único   Θ(n log n)
aleatoria_s5     415          0.060  Único   Θ(n log n)

Las 10 filas dicen Θ(n log n). Comparemos contra los teóricos para n=50:
– n log n = 50 × log₂(50) ≈ 282.
– n²/2 = 1.250.

Las comparaciones medidas (379-434) están mucho más cerca de 2·n·log n (≈564) que de n²/2 (1.250). Confirmado: heap es Θ(n log n). El “ruido” de n=15 desaparece a n=50.

Comparación cruzada con sus rivales O(n log n) sobre aleatoria_s1

Sobre la misma lista aleatoria, n=15:

Algoritmo	Comparaciones	Tiempo (ms)	Memoria extra	Estable
Heap	68	0,012	O(1)	No
Merge	40	0,010	O(n)	Sí
Quick (Lomuto)	51	0,006	O(log n)	No

Heap hace algunas comparaciones más que merge o quick, pero es el único que combina O(n log n) garantizado con memoria O(1). Quick es más rápido pero puede degradar a O(n²); merge es estable pero pide memoria. Heap es la opción “sin sorpresas + sin coste extra de memoria”.

¿Y a escala? Sobre aleatoria_s1 con n grande:

n	Comparaciones	Tiempo
100	1.036	0,14 ms
1.000	18.660	1,9 ms
10.000	235.428	26 ms

Multiplicas n por 10 → comparaciones se multiplican por ~13 (el factor del log n). Es Θ(n log n) limpio.

Reproducirlo sin instalar nada

sortlab vive privada en el Python profesional: medir, optimizar y escalar. Versión instrumentada inline:

def heap_medido(lista_original: list[int]) -> dict:
    arr = list(lista_original)
    metricas = {"comparaciones": 0, "intercambios": 0}

    def heapify(size: int, i: int) -> None:
        mayor, izq, der = i, 2 * i + 1, 2 * i + 2
        if izq < size:
            metricas["comparaciones"] += 1
            if arr[izq] > arr[mayor]:
                mayor = izq
        if der < size:
            metricas["comparaciones"] += 1
            if arr[der] > arr[mayor]:
                mayor = der
        if mayor != i:
            arr[i], arr[mayor] = arr[mayor], arr[i]
            metricas["intercambios"] += 1
            heapify(size, mayor)

    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        metricas["intercambios"] += 1
        heapify(i, 0)
    return {"ordenada": arr, **metricas}


for nombre, lista in [
    ("ordenada", list(range(1, 16))),
    ("inversa", list(range(15, 0, -1))),
    ("aleatoria_s1", [15, 11, 1, 14, 7, 6, 4, 9, 8, 12, 5, 2, 13, 10, 3]),
]:
    r = heap_medido(lista)
    print(f"{nombre:<16}  comp={r['comparaciones']:>3}  swap={r['intercambios']:>3}")

Verás cifras coherentes con la tabla.

Cuándo usar heapsort

Sí:

• Cuando necesitas O(n log n) garantizado y NO puedes permitirte memoria O(n) de merge. Heap es la respuesta: O(n log n) sin sorpresas y O(1) memoria extra.
• Como fallback dentro de Introsort. Cuando quicksort detecta que está degradando (recursión muy profunda), pasa a heapsort. C++ std::sort lo hace así.
• Para implementar colas de prioridad: la misma estructura de heap es la base de heapq en Python. Si vas a sacar siempre el mínimo o el máximo, el heap es la estructura natural.

No:

• Cuando necesitas estabilidad. Heap no la garantiza (el intercambio raíz-último salta).
• Para listas pequeñas (n < 32). Insertion sort lo bate por overhead.
• Si tienes sorted() o Arrays.sort() disponibles. Casi siempre son más rápidos en la práctica (Timsort).

Comparativa rápida

Dónde encaja heap dentro del clúster:

Algoritmo	Mejor	Peor	Memoria	Estable	Ventaja única
Quicksort	Ω(n log n)	O(n²)	O(log n)	No	Rápido en la práctica
Merge sort	Ω(n log n)	O(n log n)	O(n)	Sí	Garantiza + estable
Heap	Ω(n log n)	O(n log n)	O(1)	No	Garantiza + sin memoria
Timsort	Ω(n)	O(n log n)	O(n)	Sí	Aprovecha listas casi ordenadas

El nicho de heap es claro: cuando no puedes pagar memoria extra y necesitas la garantía O(n log n). Es la red de seguridad de Introsort y la base de las colas de prioridad.

Mitos que circulan sobre heapsort

• “Heapsort es más rápido que quicksort.” Falso en el caso medio. Quicksort gana porque tiene mejor “constante” y mejor uso del caché. Heap gana solo cuando quick degrada (peor caso). Por eso Introsort los combina.
• “El heap es la mejor estructura para ordenar.” No exactamente. El heap es eficiente para extraer máximo/mínimo repetidas veces, pero no necesariamente para “tener todo ordenado” de una sola pasada. Para eso, merge o quick suelen ser mejores en la práctica.
• “Heapsort se usa en producción.” Indirectamente, sí — como fallback de Introsort en C++. Como algoritmo principal, casi nunca. Para producción directa, los lenguajes prefieren Timsort.

¿Y en la stdlib de Python?

Sí, hay heap. El módulo heapq implementa un min-heap sobre listas:

import heapq

datos = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(datos)        # convierte en min-heap in-place
print(heapq.heappop(datos)) # 1 (el mínimo)
print(heapq.heappop(datos)) # 1
print(heapq.heappop(datos)) # 2

Y existe heapq.nlargest(k, datos) para sacar los k mayores en O(n log k) — operación clave en analítica de datos.

Lo que no hay es heapsort como función directa. Para ordenar, usa sorted() (Timsort). Heap es para cuando lo que quieres es extraer en orden uno a uno, no la lista completa de golpe.

Trivia algorítmica

Heapsort lo inventó J.W.J. Williams en 1964, publicando en Communications of the ACM. El año siguiente, Robert W. Floyd mejoró la fase de construcción del heap demostrando que es O(n), no O(n log n) como parecía a primera vista (uno de los resultados más bonitos del análisis amortizado).

FAQ rápida

¿Por qué la construcción del heap es O(n) y no O(n log n)?
Porque los nodos hoja (la mitad del árbol) no necesitan heapify. Los nodos del penúltimo nivel solo descienden un nivel. Solo la raíz desciende log n. La suma es O(n), demostrado por Floyd.

¿Heapsort se puede paralelizar?
Es difícil paralelizar la fase de extracción (cada extracción depende de la anterior). La construcción sí: heapify en paralelo de las distintas ramas.

¿Heap es lo mismo que árbol binario?
Es un tipo concreto de árbol binario: completo + propiedad de heap. La diferencia con un BST (binary search tree): un BST tiene “izquierda < raíz < derecha”; un heap solo dice “padre ≥ hijos” (sin orden entre hijos).

¿Por qué Python tiene heapq y no heapsort?
Porque el caso de uso real es “extraer en orden uno a uno” (cola de prioridad), no “ordenar todo de una”. Para ordenar, Timsort lo hace mejor.

¿Min-heap o max-heap?
Python (heapq) usa min-heap (el mínimo siempre arriba). Heapsort tradicional usa max-heap (el máximo arriba, se va sacando al final). Misma idea, sentido distinto.

En resumen

Heapsort es el algoritmo sin sorpresas y sin memoria extra. Su Θ(n log n) garantizado y su O(1) de memoria lo hacen ideal como red de seguridad de Introsort y como base de colas de prioridad. Conceptualmente es el primer puente entre arrays y árboles que ves en algoritmos: el heap es un árbol metido en un array, sin punteros, y esa idea aparece después en B-trees, índices de bases de datos y otras muchas estructuras.

Si quieres aprender a medir cuándo tu código se beneficia de una estructura como el heap y a usar heapq con criterio, ese es el camino del curso de El Pythonista.