3 - Heapsorting

É uma outra técnica de ordenação de elementos que é bastante eficiente

A técnica utiliza uma representação de dados em forma de uma árvore binária, chamada de Heap. Cada elemento do heap recebe uma numeração de 1 até N-1 e recebe um valor. A regra de preenchimento do heap é que todos os níveis devem ser preenchidos antes de passar ao nível de baixo. O nível de baixo é sempre preenchido da esquerda para a direita.

Abaixo apresentamos alguns exemplos de heap:

O heap ainda deve atender a algumas regras estruturais:

um nó pode ter no máximo dois nós filhos que sempre devem ser preenchidos da esquerda para a direita, seguindo a numeração dos nós.
o valor do nó pai deve ser sempre maior que o maior valor presente no nós filhos.