¿Cómo funciona el heap sort?

Question

Accepted Answer

**Heap sort** construye un **heap binario** a partir del array, luego extrae repetidamente el máximo para producir orden ordenado. Se ejecuta en **O(n log n)** y es **in-place**.

## La idea

Un max-heap mantiene el elemento más grande en la raíz. Construye el heap (O(n)), luego intercambia la raíz al final, reduce el heap y re-heapifica (sift down) — n veces.

## Ejemplo

```python
import heapq

def heap_sort(arr):
    heapq.heapify(arr)               # min-heap in O(n)
    return [heapq.heappop(arr)       # pop smallest n times
            for _ in range(len(arr))]

heap_sort([5, 2, 8, 1, 3])           # -> [1, 2, 3, 5, 8]
```

Una implementación clásica lo hace in-place aplicando sift down dentro del array.

## Complejidad

- **Tiempo:** O(n log n) en todos los casos. **Espacio:** O(1) in-place.

## Cuándo usar / Inconvenientes

Úsalo cuando necesites **O(n log n) garantizado** *y* **O(1) memoria extra** (merge sort necesita O(n); quicksort corre el riesgo de O(n²)). **No es estable** y tiene mala localidad de caché, por lo que a menudo es más lento en la práctica que quicksort. El mismo heap alimenta **colas de prioridad** y búsqueda de top-k elementos.

## Por qué es importante

Heap sort es el único ordenamiento común que es a la vez O(n log n) en el peor caso e in-place, haciéndolo valioso en configuraciones con memoria limitada o límites garantizados.

La estructura de heap subyacente es ampliamente útil — colas de prioridad, algoritmo de Dijkstra, y streaming top-k.

Cementa la idea de que la estructura de datos correcta hace un algoritmo eficiente.