Cómo funciona
Heap Sort usa un montículo de máximos (max-heap): un árbol binario completo
donde cada padre es siempre mayor o igual que sus hijos. No hace falta ninguna estructura aparte:
el propio array es el árbol leído por niveles. El padre de la posición i
está en ⌊(i−1)/2⌋ y sus hijos en 2i+1 y 2i+2, y la raíz
(posición 0) siempre contiene el mayor elemento.
El algoritmo tiene dos fases. Primero, construir el montículo: se hunde cada
nodo con hijos, de abajo arriba, en O(n). Después, n−1 veces: se intercambia la raíz (el máximo)
con el último elemento del montículo, el montículo encoge en 1 y se hunde la nueva raíz para
restaurar la regla. Así cada máximo queda en su posición final, de derecha a izquierda.
Paso a paso con [4, 10, 3, 5, 1]
- 01Construir (de abajo arriba): se empieza por el último nodo con hijos. Posición 1 (valor 10): sus hijos son 5 y 1, el 10 ya es mayor. Posición 0 (valor 4): sus hijos son 10 y 3, 10 > 4 → intercambio →
[10, 4, 3, 5, 1]. El 4 sigue bajando: sus hijos son 5 y 1, 5 > 4 → intercambio → [10, 5, 3, 4, 1].
- 02Extracción 1: la raíz (10) se cambia por el último (1) →
[1, 5, 3, 4, | 10]. Se hunde el 1: hijos 5 y 3, sube el 5 → [5, 1, 3, 4, | 10]. Hijo 4, sube el 4 → [5, 4, 3, 1, | 10].
- 03Extracción 2: la raíz (5) se cambia por el penúltimo (1) →
[1, 4, 3, | 5, 10]. Se hunde: sube el 4 → [4, 1, 3, | 5, 10]. Y así hasta ordenarlo todo: [1, 3, 4, 5, 10].
- ΣClave: cada hundimiento cuesta O(log n) y se hace n veces → O(n log n) en cualquier caso. A diferencia de Merge Sort, no necesita memoria extra: ordena en el propio array. No es estable: los iguales pueden cambiar de orden.
Complejidad
- Mejor caso
- O(n log n)
- Caso promedio
- O(n log n)
- Peor caso
- O(n log n)
- Espacio extra
- O(1)
- Estable
- No
- In situ
- Sí