Heapsort

Qué cubre este capítulo

Heapsort es el sort que se ve mejor en papel: O(n log n) garantizado, como merge sort, pero in place con O(1) de espacio extra, como quicksort — las buenas propiedades de ambos sin las desventajas de ninguno. Llega ahí gracias a una estructura de datos que estudiaremos a fondo dentro de dos capítulos, el heap binario: un árbol aplanado con maña dentro de un array, donde siempre puedes tomar el elemento más grande en O(log n). Heapsort construye ese heap dentro del array y luego jala el máximo al final una y otra vez. Este capítulo lo construye, observa cómo crece la región ordenada conforme se extraen los máximos, y encara el acertijo de por qué un sort con la mejor asintótica rara vez es el más rápido en la práctica.

Un poco de historia

Heapsort llegó en 1964, y con él el heap. J. W. J. Williams publicó el algoritmo e introdujo el heap binario como su motor; ese mismo año Robert Floyd demostró que el heap se podía construir en tiempo lineal, no en el O(n log n) que esperarías — un resultado que probaremos más abajo porque es genuinamente sorprendente. Juntos dieron el primer sort que era simultáneamente in place y O(n log n) garantizado, y con eso zanjaron una pregunta real de la época: ¿podías tener ambas cosas sin la memoria de merge sort ni el peor caso de quicksort? Sí podías. Heapsort se ha quedado desde entonces un poco a la sombra de quicksort — casi siempre es un poco más lento — pero nunca desaparece, porque es la red de seguridad: el introsort de tus librerías estándar de C++ y Rust es quicksort que se cambia a heapsort en cuanto un mal pivote amenaza, precisamente porque el O(n log n) de heapsort es incondicional.

La intuición

Un heap binario es un árbol aplastado dentro de un array. Pon la raíz en el índice 0; entonces, para cualquier nodo en el índice i, sus dos hijos quedan en 2i+1 y 2i+2. Esa aritmética es todo el truco — la estructura padre-hijo queda implícita en los índices, así que un heap no necesita punteros y vive completamente dentro del array. Un max-heap agrega una regla: todo padre es al menos tan grande como sus hijos, lo que significa que el elemento más grande de todo el heap siempre está en la raíz, índice 0.

Heapsort aprovecha eso en dos fases. Primero, reacomoda el array para que cumpla la regla del heap — construir el heap. Ahora el máximo está al frente. Intercámbialo con el último elemento: el máximo queda ya en su posición final al final del array, y el array vuelve a ser un heap salvo por la raíz, que probablemente es demasiado chica. "Hunde" (sift down) esa raíz — intercámbiala con su hijo mayor, una y otra vez, hasta que se asiente — y el heap queda restaurado sobre la región restante, más chica. Repite: cada paso mueve el máximo actual al final y encoge el heap en uno. La región ordenada crece desde la derecha, un máximo extraído a la vez, hasta que todo el array queda ordenado.

Complejidad: cómo escala

Cada sift-down recorre un camino de un nodo a una hoja, que a lo mucho es la altura del árbol, $O(\log n)$. Hay n extracciones, cada una con un sift-down, así que la fase de extracción es $O(n \log n)$. Construir el heap es $O(n)$ — sorprendentemente, no $O(n \log n)$, por la razón del deep-dive de más abajo — así que no cambia el total. Y todo es in place: $O(1)$ de espacio extra, puros swaps dentro del array. El mejor caso, el promedio y el peor son todos $O(n \log n)$, porque la estructura del trabajo no depende de los valores de entrada.

Ese último punto es el superpoder silencioso de heapsort, y la gráfica de consistencia lo muestra. El mismo heapsort corre sobre entrada aleatoria, ya ordenada y ordenada al revés del mismo tamaño en tiempos prácticamente idénticos — donde el pivote ingenuo de quicksort explotaba 141× con entrada ordenada, heapsort ni se inmuta:

En qué es bueno y en qué no

Heapsort es el sort para cuando el peor caso es inaceptable y al mismo tiempo la memoria escasea. Merge sort garantiza O(n log n) pero necesita O(n) de memoria; quicksort es in place pero tiene un peor caso O(n²); solo heapsort te da O(n log n) en el peor caso y espacio O(1). Esa combinación es la razón de que sea el fallback dentro de introsort y de que aparezca en sistemas de tiempo real y embebidos que no pueden tolerar ni una asignación de memoria ni una explosión cuadrática.

La razón por la que no es el default, a pesar de la mejor asintótica, es el cache. Heapsort brinca por todo el array — un padre en el índice i y su hijo en 2i+1 pueden estar lejísimos en memoria — así que maltrata el cache del CPU de una forma que los swaps locales y secuenciales de quicksort no. Big-O cuenta esos dos accesos igual; el hardware te cobra precios radicalmente distintos. El resultado es que heapsort suele ser notoriamente más lento que quicksort o un merge sort afinado en la práctica, aunque los tres sean O(n log n). Tampoco es estable. Así que heapsort es la opción que eliges por su garantía, no por su velocidad.

Los datos, o las entradas

El face-off ordena enteros aleatorios contra heapq y Timsort. La gráfica de consistencia corre heapsort sobre entrada aleatoria, ordenada e invertida para mostrar que no tiene caso malo — el contraste directo con la gráfica del peor caso de quicksort. Y la animación corre heapsort sobre doce elementos, mostrando la fase de extracción: la región ordenada creciendo desde la derecha conforme cada máximo queda fijado en su lugar.

Constrúyelo, una función a la vez

Todo el sort son dos fases — construir el heap y luego extraer el máximo n−1 veces:

def heapsort(a, probe=None):
    """O(n log n) in every case, in place. Two phases: build a max-heap (so the
    largest element is at the front), then repeatedly swap the front to the end of
    the unsorted region and sift the new front back down. The sorted region grows
    from the right as each maximum is locked into place."""
    a = list(a)
    n = len(a)
    # Phase 1 — build the max-heap bottom-up: sift every non-leaf down. This is
    # O(n), tighter than it looks (most nodes are near the bottom).
    for start in range(n // 2 - 1, -1, -1):
        _sift_down(a, start, n)
    if probe is not None:
        probe.append({"arr": list(a), "end": n})
    # Phase 2 — extract the max n-1 times. Each extraction is O(log n).
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]      # the max moves to its final position
        _sift_down(a, 0, end)            # restore the heap over the shrunk region
        if probe is not None:
            probe.append({"arr": list(a), "end": end})
    return a

Ambas fases se apoyan en una sola operación, sift-down: restaurar la propiedad de heap en un nodo hundiéndolo por debajo de cualquier hijo mayor. La aritmética de índices — hijos en 2i+1 y 2i+2 — es donde la idea del array-como-árbol se vuelve código:

def _sift_down(a, i, size):
    """Restore the max-heap property at index i within a[0:size]: while a node is
    smaller than its largest child, swap them and keep sinking. Children of i are at
    2i+1 and 2i+2 — the parent/child arithmetic is the whole reason a heap needs no
    pointers."""
    while True:
        largest = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest

Míralo funcionar

Aquí está la fase de extracción sobre doce barras. El primer frame muestra el max-heap ya construido — el elemento más grande está al frente (naranja) y el resto cumple la regla del heap (azul). Luego cada frame extrae el máximo actual: se intercambia hacia la frontera y se une a la región ordenada de la derecha (verde), y un nuevo máximo sube al frente para la siguiente ronda. Ve paso a paso y observa cómo la cola verde ordenada crece hacia la izquierda, un máximo por paso, mientras el heap azul se encoge — el array ordenándose solo, in place, sin un segundo array por ningún lado:

El código completo

Ambas versiones en un solo lugar — cambia entre ellas. La pestaña from-scratch es nuestro heapsort in place. La pestaña de librería es heapq, el heap binario de Python: haces heapify de una lista, sacas todo con pop y obtienes el orden ordenado — el mismo algoritmo pero en C. (Para ordenar de verdad seguirías llamando a sorted; el papel de heapsort en la librería es ser el fallback de introsort.)

"""Heapsort — the O(n log n) sort that's guaranteed like merge sort but in place
like quicksort. It works by turning the array into a binary max-heap and then
repeatedly pulling out the maximum.

A binary heap is a tree flattened into an array: the children of index i live at
2i+1 and 2i+2, and every parent is at least as large as its children (a max-heap).
That layout means no pointers — the array IS the tree — and it's the structure this
chapter uses to sort and the one the heaps chapter later studies in its own right.
"""


# region: heapsort
def heapsort(a, probe=None):
    """O(n log n) in every case, in place. Two phases: build a max-heap (so the
    largest element is at the front), then repeatedly swap the front to the end of
    the unsorted region and sift the new front back down. The sorted region grows
    from the right as each maximum is locked into place."""
    a = list(a)
    n = len(a)
    # Phase 1 — build the max-heap bottom-up: sift every non-leaf down. This is
    # O(n), tighter than it looks (most nodes are near the bottom).
    for start in range(n // 2 - 1, -1, -1):
        _sift_down(a, start, n)
    if probe is not None:
        probe.append({"arr": list(a), "end": n})
    # Phase 2 — extract the max n-1 times. Each extraction is O(log n).
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]      # the max moves to its final position
        _sift_down(a, 0, end)            # restore the heap over the shrunk region
        if probe is not None:
            probe.append({"arr": list(a), "end": end})
    return a
# endregion


# region: sift_down
def _sift_down(a, i, size):
    """Restore the max-heap property at index i within a[0:size]: while a node is
    smaller than its largest child, swap them and keep sinking. Children of i are at
    2i+1 and 2i+2 — the parent/child arithmetic is the whole reason a heap needs no
    pointers."""
    while True:
        largest = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest
# endregion

"""Python's `heapq` module is a binary heap (a min-heap) in C. Heapifying a list and
popping everything off yields sorted order — that's heapsort, essentially. And
`sorted` (Timsort) is what you'd actually call. Heapsort itself rarely appears as a
standalone library sort, but it's the guaranteed-O(n log n) fallback inside introsort
(the quicksort variant from last chapter), so it's always one step away.

The face-off is our heapsort against `heapq`-based sorting and against `sorted`.
"""
import heapq


# region: heapq_sort
def heapq_sort(a):
    """heapify + pop-all: a min-heap yields ascending order. Same idea as heapsort,
    implemented in C — though it builds a new list rather than sorting in place."""
    h = list(a)
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]
# endregion


# region: sort_builtin
def sort_builtin(a):
    """Timsort — the sort you'd actually reach for."""
    return sorted(a)
# endregion

Scratch vs librería

Ordenando 80000 enteros, nuestro heapsort tardó unos 148 ms contra los 7.5 ms de Timsort — como 20 veces más lento, y notablemente más lento que nuestro propio quicksort (61 ms) y merge sort (86 ms) en la misma tarea. Ese orden es la verdadera lección del capítulo: heapsort tiene el mejor perfil de Big-O de los tres y aun así pierde la carrera práctica, porque su patrón de acceso hostil al cache carga una constante que los otros no tienen. Pero échale otra mirada a la gráfica de consistencia antes de descartarlo — los números de heapsort quedaron planos con entrada aleatoria, ordenada e invertida, donde quicksort explotó. Heapsort cambia un poco de velocidad del día a día por una garantía que aguanta cualquier entrada, incluida una que elija un adversario. Ese es exactamente el trade que hace una librería cuando usa quicksort por velocidad pero deja heapsort en la reserva por seguridad.

Dónde te lo vas a encontrar de verdad

Heapsort en sí es el fallback de introsort, así que corre cada vez que std::sort o el sort inestable de Rust detecta que un pivote de quicksort va mal — lo usas sin verlo, como la garantía detrás del camino rápido. Pero el heap que está debajo es la verdadera exportación de este capítulo: la misma estructura, usada para extracción en lugar de para ordenar, es la priority queue de dentro de dos capítulos — el motor detrás de los caminos más cortos de Dijkstra, la codificación de Huffman, las simulaciones de eventos y las consultas top-k que responde heapq.nlargest. Heapsort es donde el heap se gana el sueldo por primera vez; el capítulo de heaps es donde se vuelve una herramienta por derecho propio.

Puntos clave

Heapsort construye un max-heap binario dentro del array — hijos en 2i+1 y 2i+2, sin punteros — y luego extrae el máximo n−1 veces, haciendo crecer una región ordenada desde la derecha. Es $O(n \log n)$ en todos los casos y $O(1)$ en espacio, el único sort por comparación con ambas garantías, y por eso es el fallback de confianza. Su pero está enteramente en la constante: un patrón de acceso hostil al cache lo hace más lento que quicksort en la práctica, un caso vívido de Big-O y realidad tomando caminos distintos.

Con esto se cierran los sorts por comparación, y con ellos un límite duro: cualquier sort que funcione comparando elementos necesita $\Omega(n \log n)$ comparaciones — no puedes hacerlo mejor en el caso general. El siguiente capítulo se escapa de esa cota al no comparar: cuando las llaves son enteros acotados, counting sort y radix sort corren en $O(n)$, rompiendo el límite "imposible" al usar las llaves como índices de array en lugar de compararlas.