Heap

Um heap é uma estrutura de dados organizada como árvore binária, seguindo algumas regras.

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.