How it works?

Um heap binário reside em um array comum. Para o nó no índice i (baseado em 0), seus filhos estão em 2*i + 1 e 2*i + 2. Essa indexação é todo o truque que permite que uma árvore resida em um array.

Processo Passo a Passo:

1. Construir um max-heap: rearranje o array para que cada pai seja >= seus filhos. O maior valor termina no índice 0.
2. Extrair o máximo: troque a raiz (o maior) com o último elemento do heap, então diminua o heap em um para que o maior fique agora estacionado no final em sua posição ordenada final.
3. Reparar com sift-down: a nova raiz pode estar fora de lugar, então faça o sift-down (troque-a com seu filho maior, repita) até que a propriedade do heap seja mantida novamente.
4. Repetir até que o heap esteja vazio. O array agora está ordenado de forma crescente.

Exemplo em [4, 10, 3, 5, 1]:

• Construir um max-heap: [10, 5, 3, 4, 1].
• Trocar a raiz 10 para o final e fazer o sift-down, depois repetir para 5, 4, 3.
• Resultado: [1, 3, 4, 5, 10].