Ordenamiento por Heap (Heap Sort) en Python

El heap sort es un algoritmo de ordenamiento basado en la estructura de datos heap binario. Ofrece complejidad O(n log n) en el peor caso y no requiere espacio adicional significativo, lo que lo hace ideal para entornos con memoria limitada.

1. Conceptos Fundamentales

• Heap binario: árbol completo donde cada nodo cumple la propiedad de heap (máximo o mínimo).
• Heap máximo: el valor del nodo padre es siempre mayor o igual que el de sus hijos.
• Heap mínimo: el valor del nodo padre es siempre menor o igual que el de sus hijos.

Heap Sort construye un heap máximo a partir del arreglo original y, a continuación, extrae repetidamente el elemento máximo, colocándolo al final del arreglo.

2. Implementación paso a paso en Python

import sys
def heapify(arr, n, i):
    """Mantiene la propiedad de heap para el subárbol en el índice i.
    arr – lista a ordenar
    n   – tamaño del heap (puede ser menor que len(arr) durante la fase de extracción)
    i   – índice del nodo raíz del sub‑heap"""
    largest = i          # Inicializa el mayor como raíz
    left = 2 * i + 1     # hijo izquierdo
    right = 2 * i + 2    # hijo derecho
    # Si el hijo izquierdo es mayor que la raíz
    if left < n and arr[left] > arr[largest]:
        largest = left
    # Si el hijo derecho es mayor que el mayor actual
    if right < n and arr[right] > arr[largest]:
        largest = right
    # Si el mayor no es la raíz, intercambiamos y continuamos heapificando
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
def heap_sort(arr):
    n = len(arr)
    # 1️⃣ Construir el heap máximo
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # 2️⃣ Extraer elementos del heap uno a uno
    for i in range(n - 1, 0, -1):
        # Mover la raíz (máximo) al final
        arr[0], arr[i] = arr[i], arr[0]
        # Llamar a heapify sobre el heap reducido
        heapify(arr, i, 0)
    return arr
# Ejemplo de uso
if __name__ == "__main__":
    data = [12, 11, 13, 5, 6, 7]
    print("Arreglo original:", data)
    sorted_data = heap_sort(data.copy())
    print("Ordenado con heap sort:", sorted_data)

3. Comparativa con Otros Algoritmos de Ordenamiento

4. Rendimiento y Escalabilidad

En pruebas de benchmark con 10⁶ elementos aleatorios, los tiempos típicos son:

• Quicksort (Python’s Timsort): ~0.12 s
• Heap Sort: ~0.18 s
• Merge Sort: ~0.15 s

Si la aplicación requiere memoria constante o se ejecuta en dispositivos embebidos, el trade‑off del heap sort resulta ventajoso.

5. Buenas Prácticas y Optimización

1. Usar heapq cuando solo se necesita un min‑heap simple. El módulo estándar está optimizado en C.
2. Evitar recursión profunda en heapify para listas muy grandes. Implementar una versión iterativa reduce el riesgo de RecursionError.
3. Prefetching de datos. Cuando el arreglo está en disco o en una base de datos, leer en bloques ayuda a minimizar I/O.
4. Paralelismo. En entornos multi‑core, se pueden construir varios heaps locales y después fusionarlos mediante k‑way merge.

6. Solución de Problemas Comunes

7. Seguridad y Validación de Entrada

Si el algoritmo se expone como servicio (p. ej., API de ordenación), valida que la carga útil sea una lista de números o strings seguros. Evita deserialización arbitraria y limita el tamaño máximo (por ejemplo len(arr) < 10⁶) para prevenir ataques de denegación de servicio.

8. Casos de Uso del Mundo Real

• Sistemas embebidos: ordenamiento de datos de sensores donde la memoria es escasa.
• Procesamiento de logs en tiempo real: mantener un heap de los top‑k eventos más críticos.
• Algoritmos de selección: el heap permite obtener el k‑ésimo elemento más grande en O(n log k).

9. Comparación con la Biblioteca heapq de Python

Mientras la implementación manual muestra el algoritmo completo, heapq ofrece funciones como heapify, heappush y heappop que simplifican la manipulación de min‑heaps. Para un heap sort basado en heapq:

import heapq
def heap_sort_using_heapq(iterable):
    h = list(iterable)
    heapq.heapify(h)          # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]  # O(n log n)

Esta variante es más concisa y se beneficia de la implementación C interna, aunque solo produce un orden ascendente (min‑heap).

10. Conclusión

El algoritmo de ordenamiento por heap sigue siendo una herramienta valiosa cuando se necesita un ordenamiento in‑place con garantía de complejidad O(n log n) y recursos de memoria limitados. Con las optimizaciones y buenas prácticas descritas, puedes integrar heap sort en aplicaciones críticas, desde dispositivos IoT hasta servicios de alto rendimiento.