Pesquisa · Mapa mental

Heap

Em ciência da computação, um heap (monte) é uma estrutura de dados especializada, baseada em árvore, que é essencialmente uma árvore quase completa que satisfaz a propriedade heap: se P é um nó pai de C, então a chave de P é maior que ou igual a ou menor que ou igual a chave de C. O nó no "topo" da heap é chamado de nó raiz.

Fonte: Wikipédia (pt)Atualizado em 11/10/2026
01

Exemplos

Imagem: Tambako the Jaguar · BY-ND · Openverse

Uma boa implementação de ordenação por heap geralmente implementa as instruções dispostas anteriormente como macros, como consequência, a implementação dessas operações podem ser executadas rapidamente (ver operações bit a bit). Para o filho esquerdo desloca os bits a esquerda, para o direito desloca os bits a direita 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 ciclo de clock do processador, sendo altamente eficiente.

02

Características

Imagem: eugene · BY-NC-SA · Openverse

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 de 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 raiz da árvore, enquanto no heap de mínimo a raiz armazena o menor valor existente. De maneira geral, um heap é uma forma eficiente de implementação de uma fila de prioridade, uma vez que o elemento de maior ou menor valor sempre está armazenado na primeira posição e que a remoção sempre é feita nesse mesmo elemento. 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. Assim, as inserções em uma heap são feitas sequencialmente no array em que esta é implementada, com certas manipulações para a manutenção de suas propriedades, além disto as inserções são sempre feitas nas folhas, mais precisamente na folha livre mais à esquerda, essa inserção pode não respeitar as invariantes da heap, por isso é necessário um processo chamado heapify após a inserção para garantir que as invariantes sejam mantidas.

03

Operações

Imagem: Pop!Tech · BY · Openverse

Basicamente este código irá descer o valor até o seu lugar apropriado na arvore, de forma a manter as invariantes. Este é utilizado na remoção com muita frequência. Merge (união): O método tem como objetivo juntar duas heaps retornando e transformando em uma só. Sendo uma heap representada por um array, o arrayA e o arrayB, que são as heaps que serão unidas com o objetivo de transformar-se em uma só, chamada no código de "newHeap". Considerando uma min heap, para procurar o elemento que possui a n-ésima estatística de ordem, basta considerar o seguinte código em Java:

GetParent

Considerando que heap é um array e que a posição de um nó é i, a posição do seu pai será (i - 1) / 2.

GetRight

Considerando que heap é um array e que a posição de um nó é i, a posição do seu filho da direita será (i * 2 + 1) + 1.

GetLeft

Considerando que heap é um array e que a posição de um nó é i, a posição do seu filho da esquerda será (i * 2 + 1).

04

Encaminhamento em Largura (BFS)

Breadth-first search (BFS) ou Encaminhamento em Largura é uma forma de percorrer uma árvore visitando os nós vizinhos de um determinado nível desta árvore. Por exemplo na Max-Heap à direita, percebe-se que ao analisar a Heap em sua largura, temos 4 níveis, o 1° com o valor 100, o 2° com os seguintes valores: 17, 39 e assim sucessivamente.

05

Implementações

Imagem: Guus Krol · BY-NC-ND · Openverse

Heaps podem ser implementados para fornecer o menor valor (heaps de mínimo ou min heap) ou o maior valor (heaps de máximo ou max heap). Nesse quesito, as implementações podem variar. Podem ser generalizados, entretanto, através do uso de um Comparator em Java, por exemplo, que se adaptam à situação. Outra variação comum está no index do elemento raiz (o menor elemento do heap, se for um heap de mínimo, ou o maior, se for um heap de máximo): enquanto algumas implementações optam por usar o index 0 do arranjo como raiz, outras optam por usar o index 1. Essa variação altera as operações de obter os filhos a partir do pai, e de obter o pai a partir de um dos filhos.

Implementação em C++

Os métodos mais importantes na implementação são o corrigeSubindo e o corrigeDescendo. O primeiro corrige o heap para um determinado índice recém-adicionado. É utilizado na inserção, pois para inserir um elemento em um heap podemos simplesmente adicioná-lo no final do arranjo, e depois empurrá-lo para cima na árvore enquanto ele for menor que o pai (ou maior, se for um heap de máximo). Já o corrigeDescendo realiza o mesmo processo, mas é utilizado quando o elemento precisa ser empurrado para baixo, e não para cima. Isso acontece na remoção, pois nesta operação selecionamos o último elemento do arranjo e trocamos com a raiz. Assim, podemos descartar a raiz (que está no final do arranjo agora, bastando remover o último elemento do arranjo). Porém, o último elemento do arranjo (que foi movido para a raiz) provavelmente não é o menor, e a raiz deve sempre guardar o menor elemento. Portanto, devemos empurrar o elemento para baixo até que o heap esteja corrigido. Segue uma implementação recursiva dessas duas funções:

Implementação em Java

A classe abaixo escrita em java contém o código de uma heap de seus comportamentos. É utilizado um tipo de dado genérico (generics), para que esta implementação esteja preparada para diversos tipo de objetos. Utiliza-se ainda um comparador (comparator), este é responsável por definir qual o tipo da heap, minima ou máxima.

06

Utilização

Imagem: -Reji · BY-NC-ND · Openverse

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 raiz é a maior prioridade. 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.

Vídeos recomendados

Fontes consultadas

Continue pesquisando