Ordenamiento por montículo (Heap Sort)

Mira cómo heap sort construye un max-heap y extrae el máximo al final. O(n log n) con O(1) extra — y por qué aun así se usa poco.

Algoritmo

Arreglo

Tamaño48
ComparandoIntercambioPivote/claveLecturaOrdenado
Velocidad50×

Comparaciones

0

Intercambios

0

Paso

0/665

Lecturas

0

Memoria aux.

0

Profundidad

1/1

Baja la velocidad y usa «Paso» para contrastar el resaltado del pseudocódigo con los colores de las barras. Las barras grises ya salieron del heap y quedaron fijadas.

Pseudocódigo

build max-heap (siftDown n/2→0)

for end ← n−1 down to 1

swap a[0] ↔ a[end] // 최댓값 확정

siftDown(0, end)

// child = 2·i+1, 2·i+2 중 큰 쪽과 비교

// 부모 < 자식이면 교환하며 내려감

Complejidad

MejorO(n log n)
MediaO(n log n)
PeorO(n log n)
EspacioO(1)
EstableNo

Heap sort interpreta el arreglo como árbol binario completo (hijos de i: 2i+1, 2i+2), lo convierte en max-heap (padre ≥ hijos), intercambia la raíz al final y reheapea el resto.

Construir el heap cuesta O(n) y cada extracción O(log n): O(n log n) garantizado con O(1) extra. Pierde contra quicksort por saltos de caché y ser inestable, pero sigue siendo el motor de las colas de prioridad. Visualizador de ordenamiento

Preguntas frecuentes

¿Qué es un heap?
Árbol binario completo donde cada padre supera a sus hijos (max-heap). En arreglo, los hijos de i son 2i+1 y 2i+2, sin punteros.
¿Dónde se usa heap sort?
Sistemas con memoria muy limitada, garantías de peor caso, selección de los K mayores y dentro de colas de prioridad.

Otros algoritmos