Heaps e Heapsort
Definição
Pode ser deifinida como uma árvore binária com chaves atribuídas a seus nós, uma chave por nó, na qual há duas condições que devem ser atendidas:
Shape Property
Domínio Parental
Essa árvore binária deve ser essencialmente completa, de forma que todos os níveis estão completos, exceto possívelmente no último nível onde algumas das folhas mais á direita do nível podem não existir.
A chave de cada nó devem ser maiores ou iguais comparados as chaves de seus filhos.
Formas de aplicação
Podemos também definir heap como um array H[1...n] no qual cada elemento da primeira metado do array (N/2) é maior ou igual que o elementos da segunda metade.
Duas formas de construção
Bottom-up Heap Construction
Se inicializa a árvore binária essencialmente completa com N nós ao colocar as chaves na ordem que são dadas e depois "heapfica" a árvore.
Top-down Heap Construction
Alternativa menos eficiente que "bottom-up HP", constrói uma heap por meio de inserções sucessivas de novas chaves em uma heap pré construída.
HeapSort
Um algoritmo de de ordenção de dois estágios
Estágio 1
Constrói uma Heap de um dado array
Estágio 2:
Aplica a operação de deleção de raiz n-1 vezes
Como resultado, os elementos do array são eliminados de forma decrescente. Mas como a implementaçõa de heap por array, quando um elemento deletado for o último, o array resultante será exatamente igual ao array original ordenado de forma crescente.