heapsort

Em ciência da computação, um heap é uma estrutura de dados organizada como árvore binária balanceada, seguindo algumas regras. Este pode ser implementado em um arranjo, para que ele seja acessado como uma árvore binária, usando as seguintes operações1 2 :

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