Heaps

Um heap é uma estrutura de árvore especializada de forma a satisfazer uma propriedade específica: se A é pai de B, então a chave do nó A é ordenada em relação à chave do nó B com a mesma ordenação aplicada em todo o heap. A ordenação aplicada ao heap criará um "heap máximo", quando a regra de ordenação for pais com chaves maiores que as dos filhos (Figura 1), ou um "heap mínimo", quando a regra de ordenação for pais com chaves menores que as dos filhos. Desta forma, o heap máximo apresenta o elemento com a chave de maior valor na raiz, e o heap mínimo apresenta a menor chave na raiz.

Exemplo de um heap máximo. Exemplos de Árvores

Heaps são muito úteis na implementação eficiente de filas de prioridade e em algoritmos com grafos, por exemplo na solução do problema do menor caminho, utilizando o algoritmo de Dijkstra. O algoritmo de ordenação heapsort utiliza um heap para realizar a ordenação de elementos de forma eficiente.

Embora heaps possam ter um grau arbitrário, ou até implementações com florestas, são muito comuns as implementações de heaps binários.

Implementação

Um heap é normalmente utilizado como uma fila de prioridade, e por isso, oferece operações similares a filas, com a adição de elementos sendo feita através do a operação push e a remoção do elemento no topo do heap (raiz) através da operaçào pop. Normalmente, é oferecida uma operação de consulta (peek), que retorna o maior ou menor valor de um heap, dependendo se for um heap máximo ou um heap mínimo.

Como os heaps são árvores formadas em níveis, e quando possuem grau fixo (diversos modelos de heap utilizam graus variáveis, como heap binomial ou o heap de Fibonacci) podem ser armazenadas de forma eficiente utilizando uma estrutura de array (Figura 2). Dessa forma, não há a necessidade de consumo extra de memória com a utilização de ponteiros para os filhos de um nó. Para utilizar esta representação, os filhos de um nó armazenado no índice i do array encontram-se em posições consecutivas a partir da posição \(ai+b\), onde a é o grau do heap, e b é o índice do filho (o índice do filho será 0,1,\(\ldots\) para arrays indexados por índices de base 1, ou 1,2,\(\ldots\) para arrays base 1). Para acessar o elemento que representa o pai de um outro elemento de índice i, através da Equação 1, onde \(\lfloor x \rfloor\) faz o arredondamento para baixo do valor (que pode ser substituído pela divisão inteira quando a linguagem oferecer este suporte), b é 1 para arrays de base zero e 0 para arrays de base um, e g é o grau do heap.

\[\begin{eqnarray} \lfloor \frac{i - b}{g} \rfloor \end{eqnarray}\]

Por exemplo, para armazenar um heap binário em um array (Figura 2), podemos utilizar a Equação 2, para acessar o filho à esquerda do elemento i, a Equação 3, para acessar o filho à direita do elemento i, e a Equação 4, para acessar o pai de um elemento de índice i. As Equações 2,3 e 4 podem ser utilizadas diretamente em arrays de base zero, para arrays de base um, os devidos ajustes devem ser efetuados.

\[\begin{eqnarray} esq(i) = 2 \times i + 1 \\\\ dir(i) = 2 \times i + 2 \\\\ pai(i) = \lfloor \frac{i - 1}{2} \rfloor \end{eqnarray}\]

Armazenamento de um heap binário em um array. Heap em um array

A operação pop (Algoritmo 1), implementada em um heap, armazenado em um array, deve remover o elemento na primeira posição do array e reorganizá-lo. Esta operação pode ser implementada copiando o último elemento do array para a primeira posição, diminuindo-se o número de elementos no heap, e reposicionando o elemento no topo do array fazendo com que a regra de criação do heap seja novamente válida. Esta implementação independe da regra de formação do heap, uma vez que esta será garantida pela função siftdown().

Operação pop de um heap.

pop(heap[]):
    result = heap[0]
    heap[0] = heap[heap.count - 1]
    heap.count -= 1
    siftdown(heap, 0)

A operação sift-down (Algoritmo 2), é outra operação importante em heaps, e move um elemento na direção da raiz para as folhas, mantendo a regra de formação do heap. Esta operação troca o elemento com o seu filho mais adequado, de acordo com a regra de formação do heap, se for um heap mínimo, o menor filho, se for um heap máximo (como o apresentado), o maior de seus filhos. Esta operação é executada, no máximo, o número de vezes igual a altura da árvore, que será \(\lg(N)\). Em uma implementação de heap mínimo, esta operação utilizaria index_min(), no lugar de index_max().

Operação sift-down de um heap binário.

siftdown(heap[], index):
    root = index
    swap = index_max(heap, left(index), right(index))
    swap = index_max(heap, root, swap)
    if swap != root:
        swap_values(heap, root, swap)
        siftdown(heap, swap)

A função swap_values(array, a, b) troca a posição dos elementos com índices a e b no array. A função index_max(array, a, b) retorna o valor a ou b que indexa o índice que contém o elemento de maior valor (Algoritmo 3), e deve tratar a situação onde um elemento não exista no array. Esta função é utilizada em conjunto com heaps máximos, e uma operação semelhante, index_min(), deve ser implementada para heaps mínimos.

Encontra o índice com maior elemento heap máximo.

index_max(array[], a, b):
    if b < 0 or b > array.count
        return a
    if a < 0 or a > array.count
        return b
    if array[a] > array[b]
        return a
    else
        return b

A operação push (Algoritmo 4) mostra a inserção de um novo elemento em um heap, independente da regra de formação do heap, uma vez que esta regra será garantida pela operação sift-up. Para adicionar um novo elemento no heap, basta inserí-lo como último elemento do array, e executar, nesse elemento, a operação sift-up, até que o elemento seja posicionado na posição que garanta a validade da regra de criação do heap.

Operação push de um heap.

push(heap[], value):
    heap.append(value)
    sufitup(heap, heap.count-1)

A operação sift-up (Algoritmo 5) move um elemento na direção das folhas para a raiz, trocando o elemento com o seu pai, quando os elementos violam a regra de criação do heap. Esta operação é executada, no máximo, \(\lg(N)\) vezes (a altura do heap).

Operação sift-up de um heap binário.

sifup(heap[], index):
    if index > 0:
        root = parent(index)
        if heap[index] > heap[root]
            swap_values(heap, root, index)
            siftup(heap, root)

Com as operações disponíveis, pode-se prover uma função que crie um heap a partir de um array. Esta função, heapify, pode ser implementada utilizando-se sift-up ou sift-down. Utiliando sift-up, a o heap é criado em \(O(N\lg N)\) operações (Algoritmo 6).

Operação heapify com sift-up.

heapify(array[]):
    count = 1
    while count < array.count
        siftup(heap, count)
        count += 1

Utilizando a operação sift-down, a função heapify pode ser executada com apenas \(O(N)\) operações (Algoritmo 7).

Operação heapify com sift-up.

heapify(array[]):
    n = array.count / 2
    while n >= 0
        siftdown(array, n)
        n -= 1

Apesar da semelhaça dos algoritmos, a segunda versão executará menos trocas pois, potencialmente, serão precisas menos trocas para posicionar as folhas, mesmo sendo necessárias mais operações para definir a raiz. Porém, existe apenas uma raiz, e \(2^{\lfloor \lg N \rfloor}\) folhas, e ao usar sift-down, executa-se no total, menos operações.