How it works?

Un montículo binario (binary heap) reside en un arreglo simple. Para el nodo en el índice i (basado en 0), sus hijos están en 2*i + 1 y 2*i + 2. Ese indexado es todo el truco que permite que un árbol viva en un arreglo.

Proceso paso a paso:

1. Construir un max-heap: reorganizar el arreglo para que cada padre sea >= que sus hijos. El valor más grande termina en el índice 0.
2. Extraer el máximo: intercambiar la raíz (el más grande) con el último elemento del montículo, luego reducir el tamaño del montículo en uno para que el más grande quede estacionado al final en su posición ordenada definitiva.
3. Reparar con sift-down: la nueva raíz puede estar fuera de lugar, así que hay que tamizarla hacia abajo (intercambiarla con su hijo mayor, repetir) hasta que la propiedad del montículo se cumpla de nuevo.
4. Repetir hasta que el montículo esté vacío. El arreglo ahora está ordenado de forma ascendente.

Ejemplo con [4, 10, 3, 5, 1]:

• Construir un max-heap: [10, 5, 3, 4, 1].
• Intercambiar la raíz 10 al final y aplicar sift-down, luego repetir para 5, 4, 3.
• Resultado: [1, 3, 4, 5, 10].