Heap Sort usa un heap máximo para ordenar in-place en O(n log n) garantizado. Construye un max-heap del arreglo, luego extrae el máximo repetidamente, colocando cada elemento extraído al final del arreglo.

Es el algoritmo de ordenamiento con peor caso garantizado y uso de memoria O(1) (in-place). A cambio, es inestable y generalmente más lento que QuickSort en la práctica por la menor localidad de caché.

Cómo Funciona

1. Heapify: transforma el arreglo en un max-heap (el mayor elemento en la raíz).
2. Extrae: intercambia la raíz (máximo) con el último elemento, reduce el tamaño del heap.
3. Sink: restaura la propiedad de heap en la nueva raíz (bubble-down).
4. Repite hasta que el heap esté vacío; el arreglo queda ordenado.

Idea Clave

Un max-heap garantiza que la raíz siempre sea el máximo. Si construyes el heap en O(n) (heapify bottom-up) y luego extraes n elementos en O(log n) cada uno, el total es O(n log n).

La magia de heapify en O(n) viene de que la mayoría de los nodos están en las hojas (no requieren sink). Solo los nodos internos requieren O(h) donde h es la altura, y hay pocos nodos de altura grande.

Ejemplo Trabajado

Ordena [4, 10, 3, 5, 1]:

Paso 1: Heapify (max-heap)

Árbol:      10
           /  \
         5     3
        /
       4

Arreglo: [10, 5, 3, 4, 1]

Paso 2: Extrae máximo (10)

• “Intercambia 10 con 1 (último): [1, 5, 3, 4, 10]”
• “Sink en índice 0 (valor 1):”
  • “Compara con hijos 5 y 3 → swap con 5: [5, 1, 3, 4, 10]”
  • “Compara 1 con hijos 4 (solo hijo izquierdo) → swap con 4: [5, 4, 3, 1, 10]”
• “Heap size = 4, región ordenada: [10]”

Paso 3: Extrae máximo (5)

• “Intercambia 5 con 1: [1, 4, 3, 5, 10]”
• “Sink en índice 0: swap 1 con 4 → [4, 1, 3, 5, 10]”
• “Heap size = 3, región ordenada: [5, 10]”

Paso 4: Extrae máximo (4)

• “Intercambia 4 con 3: [3, 1, 4, 5, 10]”
• “Sink en índice 0: swap 3 con 1 (no, 3 > 1) → no swap”
• “Heap size = 2, región ordenada: [4, 5, 10]”

Paso 5: Extrae máximo (3)

• “Intercambia 3 con 1: [1, 3, 4, 5, 10]”
• “Heap size = 1, región ordenada: [3, 4, 5, 10]”

Paso 6: Extrae máximo (1)

• “Heap vacío, región ordenada: [1, 3, 4, 5, 10]”

Resultado: [1, 3, 4, 5, 10]. Observa el visualizador construir el heap y extraer máximos.

Casos Extremos y Trampas

• “Arreglo ya ordenado — Heap Sort sigue construyendo el heap y extrayendo: O(n log n) sin aprovechar el orden.”
• Arreglo inverso — mismo O(n log n).
• “Estabilidad — Heap Sort es inestable: el intercambio raíz-último cambia el orden relativo.”
• Cache locality — los saltos en el heap (padre → hijo) son impredecibles para el caché, más lentos que QuickSort en la práctica.

Comparación con Otros Ordenamientos

Aplicaciones

• Sistemas embebidos — memoria limitada, peor caso garantizado
• K largest elements — encontrar los k mayores en O(n + k log n) con heap mínimo
• Priority queues — base de colas de prioridad eficientes
• Enseñanza — introduce heaps y su implementación in-place

Trayectoria de Práctica

1. Implementa sink() y heapify(); traza Heap Sort en [4, 10, 3, 5, 1].
2. Cuenta el número de comparaciones en heapify para un arreglo de 8 elementos.
3. Explica por qué Heap Sort es in-place pero inestable.
4. Compara el rendimiento real de Heap Sort vs QuickSort en arreglos aleatorios de 10,000 elementos.
5. Investiga Smoothsort: ¿cómo mejora Heap Sort para datos casi ordenados?