Heap

Em programação, particularmente, na disciplina de Computação II, um heap (monturo em inglês) é uma estrutura de dados (abstrata, implícita) para armazenamento de valores comparáveis (em Java, valores de uma classe para qual exista método compareTo()).

Heaps são úteis na implementação de filas de prioridade (priority queues, ou PQ), permitindo que operações de inserção de novos valores, e remoção do maior valor (ou menor valor, no caso de uma fila de prioridade orientada ao mínimo), sejam executadas rapidamente.

Motivação

Filas de prioridade são um tipo de estrutura de dados que fundamentalmente fazem duas operações quando implementadas:

1. Você pode colocar objetos dentro da fila de prioridade
2. Você pode tirar da fila de prioridade o objeto com maior "prioridade"

"Prioridade", nesse caso, depende do tipo de objeto na fila de prioridade. Se forem números inteiros, por exemplo, pode-se programar uma fila de prioridade que, quando você remove um elemento, sempre remove o número que tiver o maior valor. Alternativamente, pode-se programar uma que sempre remove o número de menor valor. No caso de empate (há duas ou mais entradas com a mesma prioridade, maior que a prioridade de todos os outros objetos na PQ), pode-se programar de forma que sempre remova uma das entradas com maior prioridade.

Certas formas de implementar uma fila de prioridade fazem com que inserir um novo elemento seja rápido, mas retirar o elemento de maior prioridade seja mais demorado. Outras formas fazem o contrário (inserir é devagar, enquanto retirar o de maior prioridade é rápido). Isso se deve a como é possível adicionar elementos novos arbitrariamente, mas depois é necessário descobrir qual é o de maior prioridade na hora de retirar, ou como é possível adicionar criteriosamente, para depois ser rápido retirar o maior.

Busca-se um equilíbrio, onde sempre seja relativamente rápido adicionar um elemento, e relativamente rápido retirar o elemento de maior prioridade. Isso pode ser feito enforçando, após ambas as operações, que a fila de prioridade siga algumas regras que serão descritas na sessão seguinte. Quando estas regras são obedecidas, diz-se que a estrutura que armazena os dados é um heap.

Definição

Um heap, de forma abstrata, é uma estrutura de dados onde:

1. Os objetos armazenados no heap se relacionam como uma árvore binária completa
2. Todo nó da árvore é maior ou igual (segundo algum critério de comparação) aos seus dois filhos

A afirmação 1. pode ser relaxada um pouco, (pode-se ter heaps sem ser árvores binárias, por exemplo), mas, para fins de Computação II, usa-se esta definição.

Nota-se, também, que não está se falando de árvore binária de busca (binary search tree, BST). Em uma BST, um nó pode ter filhos com valores maiores que o dele.

Quando dados estão organizados como um heap, o "maior" elemento está sempre na raíz da árvore binária. Quando se insere ou retira um elemento, não se tem a garantia que a árvore binária está organizada como um heap. Entretanto, é possível realizar operações de forma a "restaurar" a condição de heap à árvore binária, de forma rápida (se N é o número de nós da árvore, o número de comparações a serem feitas entre valores é por volta de log(N), para ambas as operações). Isso se realiza com funções de "descer" ou "subir", aplicadas aos nós da árvore.

Para "descer", se compara o valor de um nó (A) com o valor de seus filhos (se houver), e se troca a posição do pai com um dos filhos, caso esse filho tenha valor maior do que o valor do pai. Depois, se houve tal troca, o nó A, agora em outra posição, pode ter filhos diferentes. Repete-se a comparação e troca até que A não tenha filhos maiores que ele.

Para "subir", se compara o valor de um determinado nó (B) com o valor de seu pai. Se o valor de B for maior, há troca de posição. B, se houve troca, pode ter um novo pai. Repete-se a comparação e troca até que não B não tenha pai menor que ele.

Em uma fila de prioridade implementada com heap, toda adição de novo elemento é feita na posição adequada para manter a árvore binária como árvore binária completa. Após sua adição, uma possível implementação (apesar de haver outras, talvez até mais eficiêntes), é "subir" o nó adicionado até a posição adequada. Já quanto à remoção, retira-se a raíz da árvore binária, coloca-se o último elemento (segundo ordem de preenchimento de árvore binária completa) como raíz, e desce-se este até a posição adequada.

Aplicações

Heapsort é um algorítmo de ordenação pelo qual primeiro monta-se uma fila de prioridade (orientada ao mínimo, usando heap) a partir de uma sequência arbitrária de valores. Depois, repetidamente retira-se o valor de maior prioridade (nesse caso, o menor valor), sempre de modo que a propriedade de heap seja restaurada após cada remoção. Continua-se até serem removidos todos os valores do heap.

Outro potencial uso, relacionado ao heapsort, é a junção de várias sequências ordenadas em uma só sequência ordenada. Isso pode ser feito montando um heap com o próximo valor de cada uma das sequências, retirando o mínimo, e inserindo o próximo valor da sequência de onde veio o mínimo no heap.