Heap
Origem: Wikipédia, a enciclopédia livre.
Um heap é uma Estrutura de dados, que na verdade é apenas um vetor ordenado seguindo um criterio bem definido. Por exemplo, em um heap maximo o tal critério é de que a chave do elemento i do vetor é sempre maior que as chaves dos elementos 2[i]+1 e 2[i] + 2. Veja que [i] significa o piso de i, considerando a posição da raiz como zero
Exemplo : [10,5,9,3,2,7,1] é um heap de máximo.
A maneira conceitual de se "enxergar" um heap é como uma árvore completa.
Pode-se existir dois tipos de heaps: Os heaps de máximo (max heap), em que o valor de um nó qualquer da árvore é menor que o valor do nó que é seu pai; e os heaps de mínimo (min heap), em que o valor de um nó qualquer é maior que o valor do nó que é seu pai.
Com a explicação dada acima, fica claro que em um heap de máximo, o maior valor do conjunto está localizado na raiz da árvore e em um heap de mínimo, a raiz abriga o menor valor do conjunto.
Índice |
[editar] Operações
As operações mais comuns em heaps são:
[editar] Inserção
- 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 InvalidKeyException("Invalid Key");
Position z = T.add(new Item(k, e));
Position u;
while(!T.isRoot(z)) { // bubbling-up
u = T.parent(z);
if(comp.isLessThanOrEqualTo(key(u),key(z)))
break;
T.swapElements(u, z);
z = u;
}
}
[editar] Remoção
- Remoção: Remove o elemento da raiz do heap.
Codigo em Java
public Object removeMin() throws PriorityQueueEmptyException {
if(isEmpty())
throw new PriorityQueueEmptyException("Priority Queue Empty!");
Object min = element(T.root());
if(size() == 1)
T.remove();
else {
T.replaceElement(T.root(), T.remove());
Position r = T.root();
while(T.isInternal(T.leftChild(r))) {
Position s;
if(T.isExternal(T.rightChild(r)) || comp.isLessThanOrEqualTo(key(T.leftChild(r)),key(T.rightChild(r))))
s = T.leftChild(r);
else
s = T.rightChild(r);
if(comp.isLessThan(key(s), key(r))) {
T.swapElements(r, s);
r = s;
}
else
break;
}
}
}
- Merge (união): Juntar dois heaps para formar um novo heap com todos os elementos de ambos.
[editar] Utilização
Uma das utilizações mais tradicionais do heap é no algoritmo de ordenação heapsort, que utiliza a propriedade do heap de o maior (ou menor valor) localizar-se na raiz do mesmo e fazer a ordenação dos dados de uma maneira bastante eficiente.
Outra utilização de heaps são em algoritmos de seleção. Operações de encontrar o maior, ou menor, elemento de um conjunto de números é realizado de uma forma bastante eficiente, em comparação com a utilização de uma lista ligada ordenada.
