Heapsort (ordenamiento por montículo): cómo funciona, código y complejidad

La idea en palabras sencillas

Heapsort es selection sort con una forma más rápida de encontrar el máximo. Selection sort recorre toda la parte sin ordenar, O(n) cada vez. Heapsort mantiene la parte sin ordenar como un montículo, de modo que el máximo siempre está en el índice 0 y restablecer el orden tras extraerlo cuesta solo O(log n).

Un montículo binario se almacena en un arreglo simple, sin punteros. Para el elemento del índice i:

• el hijo izquierdo está en 2*i + 1 y el hijo derecho en 2*i + 2;
• el padre está en (i - 1) // 2;
• en un montículo máximo, cada padre es mayor o igual que sus hijos, así que el mayor elemento está en el índice 0.

1. Construye un montículo máximo a partir del arreglo hundiendo cada nodo que no sea hoja, empezando por el último y avanzando hasta el índice 0.
2. Intercambia la raíz (el máximo) con el último elemento del montículo. Ese elemento queda ya en su posición final.
3. Reduce el montículo en uno y hunde la nueva raíz hasta que vuelva a cumplirse la propiedad del montículo.
4. Repite los pasos 2 y 3 hasta que el montículo tenga un solo elemento.

Ejemplo resuelto, paso a paso

Ordena [4, 10, 3, 5, 1]. Los elementos posteriores a la barra están ordenados y son definitivos.

Implementación en Python

def sift_down(a, root, end):
    """Restore the max-heap property for a[root..end-1]."""
    while True:
        child = 2 * root + 1
        if child >= end:
            return
        if child + 1 < end and a[child + 1] > a[child]:
            child += 1                      # pick the larger child
        if a[root] >= a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = child

def heapsort(a):
    """Sort list a in place, ascending."""
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # build the max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]         # move the max to the end
        sift_down(a, 0, end)
    return a

print(heapsort([4, 10, 3, 5, 1]))   # [1, 3, 4, 5, 10]
print(heapsort([2, 2, 1]))          # [1, 2, 2]

El módulo heapq de Python ofrece un montículo mínimo sobre una lista simple. Extraer todos los elementos da una lista ordenada, que es un heapsort corto (no in situ):

import heapq

def heapsort_heapq(items):
    h = list(items)
    heapq.heapify(h)                       # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heapsort_heapq([4, 10, 3, 5, 1]))     # [1, 3, 4, 5, 10]
print(heapq.nlargest(2, [4, 10, 3, 5, 1]))  # [10, 5]

Complejidad temporal y espacial

Construir el montículo de abajo arriba es O(n), no O(n log n), porque la suma de las alturas de los nodos de un árbol binario completo es O(n). La fase de extracción domina el total.

Cómo se compara heapsort con otros ordenamientos

Heapsort no es estable: intercambiar la raíz con el final puede llevar un elemento más allá de otros con la misma clave. Sus principales fortalezas son un peor caso O(n log n) garantizado junto con O(1) de espacio extra, una combinación que no ofrecen ni quicksort ni merge sort. Su debilidad es el acceso a memoria: saltar entre el índice i y 2*i + 1 aprovecha mal las cachés de la CPU, por lo que suele ser más lento que un quicksort bien implementado. Introsort usa heapsort como respaldo cuando quicksort recursa demasiado profundo.

Variantes y errores comunes

• Ordenamiento parcial: para obtener solo los k mayores, construye el montículo y extrae k veces, O(n + k log n). En Python, heapq.nlargest y heapq.nsmallest lo hacen.
• Top-k de un flujo de datos: mantén un montículo mínimo de tamaño k e inserta o reemplaza cada elemento nuevo, O(n log k) de tiempo y O(k) de memoria.
• Heapsort ascendente (bottom-up) hunde primero el hueco hasta una hoja y luego lo sube, lo que ahorra comparaciones.
• Smoothsort, una variante basada en montículos de Dijkstra, se ejecuta en O(n) con entradas ya ordenadas, pero se usa poco por su complejidad.

Cuándo usar heapsort

Usa heapsort cuando necesites un peor caso O(n log n) garantizado sin memoria adicional, por ejemplo en sistemas embebidos o de tiempo real, o como respaldo de seguridad dentro de otro ordenamiento. En el código Python de uso diario, usa sorted(), que es estable y más rápido con datos típicos. El propio montículo es más útil que el ordenamiento: colas de prioridad, caminos mínimos de Dijkstra, planificadores, mezcla de k listas ordenadas (heapq.merge) y búsqueda de los k mayores valores se basan en él. Las entrevistas suelen preguntar por las fórmulas de índices del montículo, por qué construirlo es O(n) y por el problema del top-k.