Heap

 Nota: Para a área de memória dinâmica, veja Gerenciamento de memória.

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ções :

PAI(i)
   return i/2
 
ESQUERDA(i)
   return i*2
 
DIREITA(i)
   return i*2 + 1

Um arranjo acessado como uma arvore binaria balanceada.

Se estiver bem implementado estas são macros ou procedimentos "inline". Estas operações podem ser executadas rapidamente usando operações bit a bit. 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. Para encontrar o pai, desloca um bit a direita. A vantagem de usar operações bit a bit, é que cada uma delas usa apenas um clock do processador, sendo altamente eficiente.

Características

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.

Operações

As operações mais comuns em heaps são:

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;
     }
}

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.

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.

Também pode ser usada como heaps de prioridades onde a raíz é a maior prioridade. Com relação ao vetor a, inserção e remoção, é da ordem O(log(n)).

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.

Ver também

• Heapsort
• Árvores.

Bibliografia

• Cormen, T.H. ET AL. Introduction to algorithms. [S.l.]: The MIT press, 2001.