heapsort
PAI(i) return i/2 ESQUERDA(i) return i*2 DIREITA(i) return i*2 + 1
Um arranjo acessado como uma arvore binaria balanceada.1
Se estiver bem implementado estas são macros ou procedimentos "inline".2 Estas operações podem ser executadas rapidamente usando operações bit a bit.2 Para o filho esquerdo desloca os bits a esquerda, para o direito desloca os bits para a esquerda e aplica a operação "ou" com 1.2 Para encontrar o pai, desloca um bit a direita.2 A vantagem de usar operações bit a bit, é que cada uma delas usa apenas um clock do processador, sendo altamente eficiente.2
Índice [esconder]
1 Características
2 Operações
2.1 Inserção
2.2 Remoção
3 Implementações
3.1 Implementação em C++
4 Utilização
5 Referências
6 Ver também
7 Bibliografia
Características[editar | editar código-fonte]
Existem dois tipos de heaps: Os heaps de máximo (max heap), em que o valor de todos os nós são menores que os de seus respectivos pais; e os heaps de mínimo (min heap), em que o valor todos os nós são maiores que os de seus respectivos pais. Assim, em um heap de máximo, o maior valor do conjunto está na raíz da árvore, enquanto no heap de mínimo a raíz armazena o menor valor existente.
A árvore binária do heap deve estar completa até pelo menos seu penúltimo nível e, se o seu último nível não estiver completo, todos os nós do último nível deverão estar agrupados à esquerda.1
Operações[editar | editar código-fonte]
As operações mais comuns em heaps são:
Inserção[editar | editar código-fonte]
Inserção: Adicionar um novo nó ao heap..
Codigo em Java
public void insertItem(Object k, Object e) throws InvalidKeyException { if(!comp.isComparable(k)) throw new