Heap (estrutura de dados) - Heap (data structure)

Exemplo de um heap máximo binário com chaves de nó sendo inteiros entre 1 e 100

Na ciência da computação , um heap é uma estrutura de dados baseada em árvore especializada que é essencialmente uma árvore quase completa que satisfaz a propriedade heap : em um heap máximo , para qualquer nó C dado , se P for um nó pai de C, então a chave (o valor ) de P é maior ou igual à chave de C. Em um heap mínimo , a chave de P é menor ou igual à chave de C. O nó no "topo" do heap (sem pais) é chamado de nó raiz .

O heap é uma implementação com eficiência máxima de um tipo de dados abstrato denominado fila de prioridade e, na verdade, as filas de prioridade são freqüentemente chamadas de "heaps", independentemente de como possam ser implementadas. Em um heap, o elemento de prioridade mais alta (ou mais baixa) é sempre armazenado na raiz. No entanto, um heap não é uma estrutura classificada; pode ser considerado como parcialmente pedido. Um heap é uma estrutura de dados útil quando é necessário remover repetidamente o objeto com a prioridade mais alta (ou mais baixa).

Uma implementação comum de um heap é o heap binário , no qual a árvore é uma árvore binária (veja a figura). A estrutura de dados do heap, especificamente o heap binário, foi introduzida por JWJ Williams em 1964, como uma estrutura de dados para o algoritmo de classificação do heapsort . Heaps também são cruciais em vários algoritmos de gráfico eficientes , como o algoritmo de Dijkstra . Quando um heap é uma árvore binária completa, ele tem a menor altura possível - um heap com N nós e para cada nó uma ramificação sempre tem log de _uma N altura.

Observe que, conforme mostrado no gráfico, não há ordem implícita entre irmãos ou primos e nenhuma sequência implícita para uma travessia em ordem (como haveria em, por exemplo, uma árvore de pesquisa binária ). A relação de heap mencionada acima se aplica apenas entre nós e seus pais, avós, etc. O número máximo de filhos que cada nó pode ter depende do tipo de heap.

Operações

As operações comuns envolvendo heaps são:

Básico

• find-max (ou find-min ): encontre um item máximo de um heap máximo ou um item mínimo de um heap mínimo, respectivamente (também conhecido como peek )
• inserir : adicionar uma nova chave ao heap (também conhecido como push )
• extract-max (ou extract-min ): retorna o nó do valor máximo de um heap máximo [ou valor mínimo de um heap mínimo] após removê-lo do heap (também conhecido como pop )
• delete-max (ou delete-min ): removendo o nó raiz de um heap máximo (ou heap mínimo), respectivamente
• substituir : pop root e empurre uma nova chave. Mais eficiente do que pop seguido de push, uma vez que só precisa balancear uma vez, não duas, e apropriado para pilhas de tamanho fixo.

Criação

• criar heap : cria um heap vazio
• heapify : cria um heap a partir de uma determinada matriz de elementos
• merge ( união ): unir dois heaps para formar um novo heap válido contendo todos os elementos de ambos, preservando os heaps originais.
• meld : unir dois heaps para formar um novo heap válido contendo todos os elementos de ambos, destruindo os heaps originais.

Inspeção

• tamanho : retorna o número de itens no heap.
• is-empty : retorna true se o heap estiver vazio, false caso contrário.

interno

• tecla de aumento ou tecla de diminuição : atualização de uma chave em um heap máximo ou mínimo, respectivamente
• excluir : exclui um nó arbitrário (seguido por mover o último nó e peneirar para manter o heap)
• peneirar : mover um nó para cima na árvore, enquanto for necessário; usado para restaurar a condição de heap após a inserção. Chamado de " peneira " porque o nó sobe na árvore até atingir o nível correto, como em uma peneira .
• peneirar para baixo : move um nó para baixo na árvore, semelhante a peneirar para cima; usado para restaurar a condição de heap após exclusão ou substituição.

Implementação

Heaps geralmente são implementados com uma matriz , da seguinte maneira:

• Cada elemento da matriz representa um nó da pilha, e
• O relacionamento pai / filho é definido implicitamente pelos índices dos elementos na matriz.

Exemplo de um heap máximo binário completo com chaves de nó sendo inteiros de 1 a 100 e como ele seria armazenado em uma matriz.

Para um heap binário , na matriz, o primeiro índice contém o elemento raiz. Os próximos dois índices da matriz contêm os filhos da raiz. Os próximos quatro índices contêm os quatro filhos dos dois nós filhos da raiz e assim por diante. Portanto, dado um nó no índice i , seus filhos estão nos índices 2i + 1 e 2i + 2 , e seu pai está no índice ⌊ (i − 1) / 2⌋ . Esse esquema de indexação simples torna eficiente mover "para cima" ou "para baixo" na árvore.

O equilíbrio de um heap é feito por operações de peneiramento ou peneiramento (troca de elementos que estão fora de ordem). Como podemos construir um heap a partir de um array sem exigir memória extra (para os nós, por exemplo), o heapsort pode ser usado para classificar um array no local.

Depois que um elemento é inserido ou excluído de um heap, a propriedade do heap pode ser violada e o heap deve ser reequilibrado trocando-se os elementos dentro da matriz.

Embora diferentes tipos de heap implementem as operações de maneira diferente, a maneira mais comum é a seguinte:
Inserção: Adicione o novo elemento no final do heap, no primeiro espaço livre disponível. Isso violará a propriedade de heap, portanto, os elementos são deslocados para cima (ou operação de nadar ) até que a propriedade de heap seja restabelecida.
Extração: Remova a raiz e insira o último elemento do heap na raiz e isso violará a propriedade do heap, portanto, peneire para restabelecer a propriedade do heap (ou operação de coletor ). Assim, a substituição é feita excluindo a raiz e colocando o novo elemento na raiz e peneirando para baixo, evitando uma etapa de peneiramento para cima em comparação com pop (peneirar para baixo do último elemento) seguido de push (peneirar para cima do novo elemento).

A construção de um heap binário (ou d -ary) a partir de uma determinada matriz de elementos pode ser realizada em tempo linear usando o algoritmo Floyd clássico , com o número de pior caso de comparações igual a 2 N - 2 s ₂ ( N ) - e ₂ ( N ) (para uma pilha binário), que s _dois ( N ) representa a soma de todos os dígitos da representação binária de N e e ₂ ( N ) é o expoente de 2 em fatorização primo de N . Isso é mais rápido do que uma sequência de inserções consecutivas em um heap originalmente vazio, que é log-linear.

Variantes

Comparação de limites teóricos para variantes

Aqui estão as complexidades de tempo de várias estruturas de dados de heap. Os nomes das funções assumem um heap máximo. Para o significado de " O ( f )" e " Θ ( f )" ver Big O notação .

Formulários

A estrutura de dados de heap possui muitos aplicativos.

• Heapsort : Um dos melhores métodos de classificação implementado e sem cenários de pior caso quadrático.
• Algoritmos de seleção : um heap permite o acesso ao elemento mínimo ou máximo em tempo constante, e outras seleções (como mediana ou k-ésimo elemento) podem ser feitas em tempo sublinear nos dados que estão em um heap.
• Algoritmos de gráfico : usando heaps como estruturas de dados de passagem interna, o tempo de execução será reduzido por ordem polinomial. Exemplos de tais problemas são o algoritmo de árvore geradora mínima de Prim e o algoritmo de caminho mais curto de Dijkstra .
• Fila de prioridade : Uma fila de prioridade é um conceito abstrato como "uma lista" ou "um mapa"; assim como uma lista pode ser implementada com uma lista vinculada ou uma matriz, uma fila de prioridade pode ser implementada com um heap ou uma variedade de outros métodos.
• Mesclagem K-way : Uma estrutura de dados heap é útil para mesclar muitos fluxos de entrada já classificados em um único fluxo de saída classificado. Exemplos da necessidade de mesclagem incluem classificação externa e resultados de streaming de dados distribuídos, como uma árvore de mesclagem estruturada de log. O loop interno está obtendo o elemento min, substituindo pelo próximo elemento para o fluxo de entrada correspondente e, em seguida, fazendo uma operação de pilha de peneiramento. (Como alternativa, a função replace.) (Usar as funções extract-max e insert de uma fila de prioridade são muito menos eficientes.)
• Estatísticas do pedido : a estrutura de dados Heap pode ser usada para encontrar com eficiência o k-ésimo menor (ou maior) elemento em uma matriz.

Implementações de linguagem de programação

• A C ++ Standard Library fornece os algoritmos make_heap , push_heap e pop_heap para heaps (geralmente implementados como heaps binários), que operam em iteradores arbitrários de acesso aleatório . Ele trata os iteradores como uma referência a uma matriz e usa a conversão de matriz em heap. Ele também fornece o adaptador de contêiner priority_queue , que envolve esses recursos em uma classe semelhante a um contêiner. No entanto, não há suporte padrão para as operações de substituição, peneiração para cima / para baixo ou para diminuir / aumentar.
• As bibliotecas Boost C ++ incluem uma biblioteca heaps. Ao contrário do STL, ele suporta operações de diminuição e aumento e suporta tipos adicionais de heap: especificamente, ele suporta d -ary, binomial, Fibonacci, emparelhamento e skew heaps.
• Há uma implementação de heap genérico para C e C ++ com suporte de heap D-ário e heap B. Ele fornece uma API semelhante a STL.
• A biblioteca padrão da linguagem de programação D inclui std.container.BinaryHeap , que é implementado em termos de intervalos de D's . As instâncias podem ser construídas a partir de qualquer intervalo de acesso aleatório . BinaryHeap expõe uma interface de intervalo de entrada que permite a iteração com instruções foreach integradas de D e integração com a API baseada em intervalo do pacote std.algorithm .
• A plataforma Java (desde a versão 1.5) fornece uma implementação de heap binário com a classe java.util.PriorityQueueno Java Collections Framework . Esta classe implementa por padrão um min-heap; para implementar um heap máximo, o programador deve escrever um comparador personalizado. Não há suporte para as operações de substituição, filtragem para cima / para baixo ou diminuição / aumento de teclas.
• Python tem um módulo heapq que implementa uma fila de prioridade usando um heap binário. A biblioteca expõe uma função heapreplace para suportar a fusão k-way.
• O PHP possui tanto o heap máximo ( SplMaxHeap ) quanto o heap mínimo ( SplMinHeap ) a partir da versão 5.3 na Biblioteca PHP padrão.
• Perl tem implementações de heaps binários, binomiais e Fibonacci na distribuição Heap disponível no CPAN .
• A linguagem Go contém um pacote de heap com algoritmos de heap que operam em um tipo arbitrário que satisfaz uma determinada interface. Esse pacote não suporta as operações de substituição, filtragem para cima / para baixo ou diminuição / aumento de teclas.
• A biblioteca Core Foundation da Apple contém uma estrutura CFBinaryHeap .
• Pharo tem uma implementação de um heap no pacote Collections-Sequenceable junto com um conjunto de casos de teste. Um heap é usado na implementação do loop de eventos do cronômetro.
• A linguagem de programação Rust tem uma implementação de heap máximo binário, BinaryHeap , no módulo de coleções de sua biblioteca padrão.

Veja também

• Algoritmo de classificação
• Estrutura de dados de pesquisa
• Pilha (tipo de dados abstratos)
• Fila (tipo de dados abstratos)
• Árvore (estrutura de dados)
• Treap , uma forma de árvore de pesquisa binária baseada em árvores ordenadas por heap

Referências

links externos

• Pilha em Wolfram MathWorld
• Explicação de como funcionam os algoritmos de heap básicos
• Bentley, Jon Louis (2000). Pérolas de programação (2ª ed.). Addison Wesley. pp. 147-162. ISBN 0201657880.