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
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
| Mejor | O(n log n) |
|---|---|
| Media | O(n log n) |
| Peor | O(n log n) |
| Espacio | O(1) |
| Estable | No |
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