Heap Sort: Ordenando con Árboles Binarios

Si Bubble Sort es fuerza bruta, Heap Sort es arquitectura inteligente. Este algoritmo no solo ordena; primero organiza los datos en una estructura muy específica llamada Heap (Montículo) para facilitar el trabajo.

El concepto: Max-Heap

Un Heap es una forma de visualizar un array como si fuera un árbol binario. En un Max-Heap, el “padre” siempre es mayor que sus “hijos”. Esto garantiza una propiedad vital: el elemento más grande de todo el conjunto siempre está en la raíz (el inicio del array).

🏁 Carrera de Algoritmos

Mismo set de datos (50 elementos). ¿Quién gana?

Bubble Sort 0.00s

🏆

Heap Sort 0.00s

🏆

Quick Sort 0.00s

🏆

El Algoritmo

Construir el Heap: Convertimos nuestra lista desordenada en un Max-Heap. Ahora sabemos que el primer elemento es el máximo.
Extracción:
- Tomamos el primer elemento (el mayor) y lo intercambiamos con el último del array.
- Consideramos ese último elemento como “ya ordenado” y lo ignoramos.
- “Reparamos” el Heap (Heapify) para que el nuevo primer elemento sea el siguiente mayor.
- Repetimos hasta que no queden elementos.

El Código (Python)

def heapify(arr, n, i):
    largest = i   # Inicializar el más grande como raíz
    l = 2 * i + 1 # izquierda
    r = 2 * i + 2 # derecha

    # Ver si el hijo izquierdo existe y es mayor que la raíz
    if l < n and arr[l] > arr[largest]:
        largest = l

    # Ver si el hijo derecho existe y es mayor que la raíz
    if r < n and arr[r] > arr[largest]:
        largest = r

    # Cambiar la raíz si es necesario
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i] # Swap
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # Construir un maxheap.
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extraer elementos uno a uno
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i] # Swap
        heapify(arr, i, 0)

Rendimiento: O(n log n)

A diferencia de Bubble Sort, Heap Sort es muy eficiente. Su complejidad es O(n log n) tanto en el mejor como en el peor de los casos.

Ventajas y Desventajas

Pro: No usa memoria extra (es in-place), a diferencia de Merge Sort.
Pro: Muy consistente. No hay “casos malos” que lo hagan lento.
Contra: No es “estable” (puede cambiar el orden relativo de elementos iguales).
Contra: En la práctica, suele ser un poco más lento que Quick Sort debido a cómo accede a la memoria (saltando índices).

SincroDev