5 - HeapSort

HeapSort combina un montículo binario con un esquema in-place para lograr O(n log n) en todos los casos, sin memoria extra significativa. Es útil cuando queremos evitar el peor caso de QuickSort y minimizar el uso de pila.

5.1 ¿Qué es un heap?

Un heap binario es un árbol completo donde cada nodo es mayor o igual (max-heap) o menor o igual (min-heap) que sus hijos. Esto permite extraer el máximo o mínimo en O(log n).

5.2 Representación en listas

Un heap completo se mapea en una lista de forma contigua:

• Hijo izquierdo de i: 2 * i + 1
• Hijo derecho de i: 2 * i + 2
• Padre de i: (i - 1) / 2

5.3 Construcción del heap (heapify)

Construimos un max-heap en tiempo lineal recorriendo desde el último nodo interno hacia la raíz y aplicando sift-down:

def sift_down(arr, n, i):
  mayor = i
  hijo_izq = 2 * i + 1
  hijo_der = 2 * i + 2

  if hijo_izq < n and arr[hijo_izq] > arr[mayor]:
    mayor = hijo_izq
  if hijo_der < n and arr[hijo_der] > arr[mayor]:
    mayor = hijo_der
  if mayor != i:
    arr[i], arr[mayor] = arr[mayor], arr[i]
    sift_down(arr, n, mayor)

def heapify(arr):
  n = len(arr)
  for i in range((n // 2) - 1, -1, -1):
    sift_down(arr, n, i)

5.4 Operación sift-down

sift_down garantiza que el nodo i cumpla la propiedad de heap, desplazando el valor hacia abajo hasta que sea mayor que sus hijos. Es la operación clave en heapify y en cada extracción.

5.5 Extracción del máximo

Para ordenar de forma ascendente con un max-heap:

• Intercambiamos la raíz (máximo) con el último elemento.
• Reducimos el tamaño lógico del heap.
• Aplicamos sift_down en la raíz para restaurar el orden.

5.6 HeapSort paso a paso

def heapsort(arr):
  heapify(arr)
  for fin in range(len(arr) - 1, 0, -1):
    arr[0], arr[fin] = arr[fin], arr[0]
    sift_down(arr, fin, 0)  # heap reducido

5.7 Implementación completa en Python

Unificación de las funciones clave:

def sift_down(arr, n, i):
  mayor = i
  hijo_izq = 2 * i + 1
  hijo_der = 2 * i + 2
  if hijo_izq < n and arr[hijo_izq] > arr[mayor]:
    mayor = hijo_izq
  if hijo_der < n and arr[hijo_der] > arr[mayor]:
    mayor = hijo_der
  if mayor != i:
    arr[i], arr[mayor] = arr[mayor], arr[i]
    sift_down(arr, n, mayor)

def heapify(arr):
  n = len(arr)
  for i in range((n // 2) - 1, -1, -1):
    sift_down(arr, n, i)

def heapsort(arr):
  heapify(arr)
  for fin in range(len(arr) - 1, 0, -1):
    arr[0], arr[fin] = arr[fin], arr[0]
    sift_down(arr, fin, 0)

5.8 Costos temporales y espaciales

• Tiempo: O(n log n) en todos los casos.
• Memoria: O(1) adicional; trabaja in-place.
• Estabilidad: no es estable.

5.9 Ventajas y desventajas

• Ventajas: garantiza O(n log n) sin riesgo de peor caso cuadrático; in-place; no depende de recursión profunda.
• Desventajas: no es estable; las constantes pueden ser mayores que QuickSort en promedio; acceso menos cache-friendly.

5.10 Casos donde HeapSort supera a QuickSort

• Entradas adversas o diseñadas para forzar peores casos en QuickSort.
• Ambientes con límites estrictos de pila o donde la recursión está restringida.
• Necesidad de garantizar complejidad acotada sin riesgo de degradación.

5.11 Archivo único de trabajo

Siguiendo el formato del tutorial, reunimos todo en ordenamientos.py para ejecutar rápido.

# archivo: ordenamientos.py
def sift_down(arr, n, i):
  mayor = i
  hijo_izq = 2 * i + 1
  hijo_der = 2 * i + 2
  if hijo_izq < n and arr[hijo_izq] > arr[mayor]:
    mayor = hijo_izq
  if hijo_der < n and arr[hijo_der] > arr[mayor]:
    mayor = hijo_der
  if mayor != i:
    arr[i], arr[mayor] = arr[mayor], arr[i]
    sift_down(arr, n, mayor)

def heapify(arr):
  n = len(arr)
  for i in range((n // 2) - 1, -1, -1):
    sift_down(arr, n, i)

def heapsort(arr):
  heapify(arr)
  for fin in range(len(arr) - 1, 0, -1):
    arr[0], arr[fin] = arr[fin], arr[0]
    sift_down(arr, fin, 0)

datos = [16, 7, 3, 20, 17, 8, 10, 1]
heapsort(datos)
print(datos)

Con esta base puedes ajustar el esquema de sift_down o instrumentar conteos de comparaciones sin cambiar la interfaz.