Overview
Heap Sort construye un max-heap y en cada paso mueve el mayor al final.
Analogy
Como una cola de prioridad: siempre sale primero el valor mas grande.
Step-by-step
- Convertir el arreglo a max-heap (heapify).
- Intercambiar la raiz con el ultimo elemento no ordenado.
- Reducir heap_size en 1.
- Aplicar sift-down desde la raiz.
- Repetir hasta heap_size = 1.
Visual
[heap | sorted tail]: la parte ordenada crece a la derecha.
Common mistakes
- Confundir formulas de hijos en base 0 vs base 1.
- No reducir heap_size tras cada extraccion.
- Usar sift-up cuando toca sift-down.
Practice questions
- Haz heapify de [4,10,3,5,1] paso a paso.
- Explica por que Heap Sort no es estable.
- Adapta a min-heap para ordenar descendente.