Phenquestions
Ilustração de estruturas de dados heap
Existem dois tipos de heap: um heap máximo e um heap mínimo. Uma estrutura de heap máximo é onde o valor máximo é a raiz e os valores se tornam menores à medida que a árvore desce; qualquer pai é igual ou maior em valor do que qualquer um de seus filhos imediatos. Uma estrutura de pilha mínima é onde o valor mínimo é a raiz e os valores se tornam maiores à medida que a árvore desce; qualquer pai é igual ou menor em valor do que qualquer um de seus filhos imediatos. Nos diagramas a seguir, o primeiro é um heap máximo e o segundo é um heap mínimo:
Para ambos os montes, observe que para um par de crianças, não importa se o da esquerda é o maior valor. Uma linha em um nível da árvore, não deve necessariamente ser preenchida do mínimo ao máximo, da esquerda; também não é necessariamente preenchido do máximo para o mínimo, da esquerda.
Representando um Heap em uma Matriz
Para que o software use um heap facilmente, o heap deve ser representado em uma matriz. O heap máximo acima, representado em uma matriz, é:
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69Isso é feito começando com o valor da raiz como o primeiro valor para a matriz. Os valores são colocados continuamente lendo a árvore da esquerda para a direita, de cima para baixo. Se um elemento estiver ausente, sua posição na matriz será ignorada. Cada nó tem dois filhos. Se um nó está no índice (posição) n, seu primeiro filho na matriz está no índice 2n + 1, e seu próximo filho está no índice 2n + 2. 89 está no índice 0; seu primeiro filho, 85 está no índice 2 (0) + 1 = 1, enquanto seu segundo filho está no índice 2 (0) + 2 = 2. 85 está no índice 1; seu primeiro filho, 84, está no índice 2 (1) + 1 = 3, enquanto seu segundo filho, 82 está no índice 2 (1) + 2 = 4. 79 está no índice 5; seu primeiro filho, 65, está no índice 2 (5) + 1 = 11, enquanto seu segundo filho está no índice 2 (5) + 2 = 12. As fórmulas são aplicadas ao resto dos elementos da matriz.
Essa matriz, em que o significado de um elemento e a relação entre os elementos está implícito na posição do elemento, é chamada de Estrutura de Dados Implícita.
A estrutura de dados implícita para o heap mínimo acima é:
65, 68, 70, 73, 71, 83, 84,,, 79, 80,,, 85, 89O heap máximo acima é uma árvore binária completa, mas não uma árvore binária completa. É por isso que alguns locais (posições) estão vazios na matriz. Para uma árvore binária completa, nenhum local ficará vazio na matriz.
Agora, se o heap fosse uma árvore quase completa, por exemplo, se o valor 82 estivesse faltando, a matriz seria:
89, 85, 87, 84,, 79, 73, 80, 81,,, 65, 69Nesta situação, três locais estão vazios. No entanto, as fórmulas ainda são aplicáveis.
Operações
Uma estrutura de dados é um formato de dados (e.g. uma árvore), mais a relação entre os valores, mais as operações (funções) executadas nos valores. Para um heap, o relacionamento que percorre todo o heap é que o pai deve ser igual ou maior em valor do que os filhos, para um heap máximo; e o pai deve ser igual ou menor em valor do que os filhos, para um min-heap. Esta relação é chamada de propriedade heap. As operações de um heap são agrupadas sob os títulos de Criação, Básico, Interno e Inspeção. A seguir, um resumo das operações do heap:
Resumo de operações de heap
Existem certas operações de software que são comuns com heaps, como segue:
Criação de um Heap
create_heap: Criar um heap significa formar um objeto que representa o heap. Na linguagem C, você pode criar um heap com o tipo de objeto de estrutura. Um dos membros da estrutura será a matriz de heap. O resto dos membros serão funções (operações) para o heap. Create_heap significa criar um heap vazio.
Heapify: a matriz de heap é uma matriz parcialmente classificada (ordenada). Heapify significa, fornecer um array de heap de um array não classificado - veja os detalhes abaixo.
Merge: Isto significa, formar um heap de união a partir de dois heaps diferentes - veja os detalhes abaixo. Os dois heaps devem ser heap máximo ou heap mínimo. O novo heap está em conformidade com a propriedade heap, enquanto os heaps originais são preservados (não apagados).
Combinar: Isso significa juntar dois montes do mesmo tipo para formar um novo, mantendo duplicatas - veja os detalhes abaixo. O novo heap está em conformidade com a propriedade heap, enquanto os heaps originais são destruídos (apagados). A principal diferença entre a fusão e a fusão é que, para a fusão, uma árvore se ajusta como uma subárvore à raiz da outra árvore, permitindo valores duplicados na nova árvore, enquanto para a fusão, uma nova árvore de heap é formada, removendo as duplicatas. Não há necessidade de manter as duas pilhas originais com fusão.
Operações básicas de heap
find_max (find_min): Localize o valor máximo na matriz de heap máximo e retorne uma cópia ou localize o valor mínimo na matriz de heap mínimo e retorne uma cópia.
Inserir: adicione um novo elemento à matriz de heap e reorganize a matriz de modo que a propriedade de heap do diagrama seja mantida.
extract_max (extract_min): Localize o valor máximo na matriz de heap máximo, remova-o e retorne-o; ou localize o valor mínimo na matriz min-heap, remova e retorne-o.
delete_max (delete_min): Localize o nó raiz de um heap máximo, que é o primeiro elemento da matriz de heap máximo, remova-o sem necessariamente retorná-lo; ou localize o nó raiz de um min-heap, que é o primeiro elemento da matriz min-heap, remova-o sem necessariamente retorná-lo;
Substituir: localize o nó raiz de qualquer heap, remova-o e substitua-o por um novo. Não importa se a raiz antiga é retornada.
Operações Heap Internas
aumentar_key (diminuir_key): Aumentar o valor de qualquer nó para um heap máximo e reorganizar para que a propriedade heap seja mantida, ou diminuir o valor de qualquer nó para um heap mínimo e reorganizar para que a propriedade heap seja mantida.
Excluir: exclua qualquer nó e, em seguida, reorganize, de modo que a propriedade heap seja mantida para o heap máximo ou um heap mínimo.
shift_up: move um nó para cima em um heap máximo ou heap mínimo enquanto for necessário, reorganizando para manter a propriedade de heap.
shift_down: mova um nó para baixo em um heap máximo ou heap mínimo enquanto for necessário, reorganizando para manter a propriedade de heap.
Inspeção de um Heap
Tamanho: Isso retorna o número de chaves (valores) em um heap; não inclui os locais vazios da matriz de heap. Um heap pode ser representado por código, como no diagrama, ou com uma matriz.
está vazia: Isso retorna booleano verdadeiro se não houver nenhum nó em um heap ou booleano falso se o heap tiver pelo menos um nó.
Peneirando em uma Pilha
Há peneiramento para cima e para baixo:
Peneirar: Isso significa trocar um nó por seu pai. Se a propriedade heap não for satisfeita, troque o pai por seu próprio pai. Continue assim no caminho até que a propriedade heap seja satisfeita. O procedimento pode chegar à raiz.
Peneirar para baixo: Isso significa trocar um nó de grande valor com o menor de seus dois filhos (ou um filho para um heap quase completo). Se a propriedade heap não for satisfeita, troque o nó inferior pelo nó menor de seus próprios dois filhos. Continue assim no caminho até que a propriedade heap seja satisfeita. O procedimento pode chegar a uma folha.
Heapifying
Heapify significa classificar uma matriz não classificada para ter a propriedade heap satisfeita para heap máximo ou heap mínimo. Isso significa que pode haver alguns locais vazios na nova matriz. O algoritmo básico para heapar um heap máximo ou heap mínimo é o seguinte:
- se o nó raiz for mais extremo do que qualquer um dos nós filho, então troque a raiz com o nó filho menos extremo.
- Repita esta etapa com os nós filhos em um esquema de travessia de árvore de pré-pedido.
A árvore final é uma árvore de heap que satisfaz a propriedade de heap. Um heap pode ser representado como um diagrama de árvore ou em uma matriz. O heap resultante é uma árvore parcialmente classificada, i.e. uma matriz parcialmente classificada.
Detalhes da operação de heap
Esta seção do artigo fornece os detalhes das operações de heap.
Criação de um Heap Details
create_heap
Veja acima!
heapificar
Veja acima
fundir
Se as matrizes de heap,
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69e
89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71são mesclados, o resultado sem duplicatas pode ser,
89, 85, 87, 84, 82, 83, 81, 80, 79,, 73, 68, 65, 69, 70, 71Depois de alguma peneiração. Observe que na primeira matriz, 82 não tem filhos. Na matriz resultante, está no índice 4; e seus locais no índice 2 (4) + 1 = 9 e 2 (4) + 2 = 10 estão vazios. Isso significa que também não tem filhos no novo diagrama de árvore. Os dois heaps originais não devem ser excluídos, pois suas informações não estão realmente no novo heap (nova matriz). O algoritmo básico para mesclar heaps do mesmo tipo é o seguinte:
- Junte uma matriz à parte inferior da outra matriz.
- Heapify está eliminando duplicatas, certificando-se de que os nós que não tinham filhos nos heaps originais ainda não tenham filhos no novo heap.
fundir
O algoritmo para fundir dois montes do mesmo tipo (dois máx- ou dois min-) é o seguinte:
- Compare os dois nós raiz.
- Faça a raiz menos extrema e o resto de sua árvore (subárvore), o segundo filho da raiz extrema.
- Peneire a criança perdida da raiz de agora a subárvore extrema, para baixo na subárvore extrema.
O heap resultante ainda está em conformidade com a propriedade heap, enquanto os heaps originais são destruídos (apagados). Os heaps originais podem ser destruídos porque todas as informações que eles possuíam ainda estão no novo heap.
Operações básicas de heap
find_max (find_min)
Isso significa localizar o valor máximo na matriz de heap máximo e retornar uma cópia ou localizar o valor mínimo na matriz de heap mínimo e retornar uma cópia. Uma matriz de heap, por definição, já satisfaz a propriedade de heap. Então, basta retornar uma cópia do primeiro elemento da matriz.
inserir
Isso significa adicionar um novo elemento à matriz de heap e reorganizar a matriz de modo que a propriedade de heap do diagrama seja mantida (satisfeita). O algoritmo para fazer isso para os dois tipos de heaps é o seguinte:
- Assuma uma árvore binária completa. Isso significa que a matriz deve ser preenchida no final com locais vazios, se necessário. O número total de nós de um heap completo é 1 ou 3 ou 7 ou 15 ou 31, etc.; continue dobrando e adicionando 1.
- Coloque o nó no local vazio mais adequado por magnitude, próximo ao final do heap (próximo ao final da matriz de heap). Se não houver um local vazio, comece uma nova linha do canto inferior esquerdo.
- Peneire se necessário, até que a propriedade de heap seja satisfeita.
extract_max (extract_min)
Localize o valor máximo na matriz de heap máximo, remova-o e retorne-o; ou localize o valor mínimo na matriz min-heap, remova e retorne-o. O algoritmo para extract_max (extract_min) é o seguinte:
- Remova o nó raiz.
- Pegue (remova) o nó inferior direito (último nó na matriz) e coloque na raiz.
- Peneire conforme apropriado, até que a propriedade de heap seja satisfeita.
delete_max (delete_min)
Localize o nó raiz de um heap máximo, que é o primeiro elemento da matriz de heap máximo, remova-o sem necessariamente retorná-lo; ou localize o nó raiz de um min-heap, que é o primeiro elemento da matriz min-heap, remova-o sem necessariamente retorná-lo. O algoritmo para excluir o nó raiz é o seguinte:
- Remova o nó raiz.
- Pegue (remova) o nó inferior direito (último nó na matriz) e coloque na raiz.
- Peneire conforme apropriado, até que a propriedade de heap seja satisfeita.
substituir
Localize o nó raiz de qualquer heap, remova-o e substitua-o pelo novo. Não importa se a raiz antiga é retornada. Peneire se apropriado, até que a propriedade de heap seja satisfeita.
Operações Heap Internas
aumentar_chave (diminuir_chave)
Aumente o valor de qualquer nó para um heap máximo e reorganize para que a propriedade de heap seja mantida ou diminua o valor de qualquer nó para um heap mínimo e reorganize para que a propriedade de heap seja mantida. Peneire para cima ou para baixo conforme apropriado, até que a propriedade de heap seja satisfeita.
excluir
Remova o nó de interesse e, em seguida, reorganize-o, de modo que a propriedade de heap seja mantida para o heap máximo ou heap mínimo. O algoritmo para excluir um nó é o seguinte:
- Remova o nó de interesse.
- Pegue (remova) o nó inferior direito (último nó na matriz) e coloque no índice do nó removido. Se o nó excluído estiver na última linha, isso pode não ser necessário.
- Peneire para cima ou para baixo conforme apropriado, até que a propriedade de heap seja satisfeita.
shift_up
Mova um nó para cima em um heap máximo ou heap mínimo enquanto for necessário, reorganizando para manter a propriedade de heap - peneire.
shift_down
Mova um nó para baixo em um heap máximo ou mínimo pelo tempo que for necessário, reorganizando para manter a propriedade de heap - peneirar.
Inspeção de um Heap
Tamanho
Veja acima!
está vazia
Veja acima!
Outras classes de montões
O heap descrito neste artigo pode ser considerado como o heap principal (geral). Existem outras classes de pilhas. No entanto, os dois que você deve saber além disso são o Heap Binário e o Heap d-ário.
Pilha Binária
O heap binário é semelhante a este heap principal, mas com mais restrições. Em particular, o heap binário deve ser uma árvore completa. Não confunda entre uma árvore completa e uma árvore inteira.
Heap d-ário
Uma pilha binária é uma pilha 2-ária. Um heap em que cada nó tem 3 filhos é um heap 3-ário. Um heap em que cada nó tem 4 filhos é um heap 4 ário e assim por diante. Um monte d-ário tem outras restrições.
Conclusão
Um heap é uma árvore binária completa ou quase completa, que satisfaz a propriedade heap. A propriedade heap tem 2 alternativas: para um heap máximo, um pai deve ser igual ou maior em valor do que os filhos imediatos; para um heap mínimo, um pai deve ter valor igual ou inferior ao dos filhos imediatos. Um heap pode ser representado como uma árvore ou em uma matriz. Quando representado em uma matriz, o nó raiz é o primeiro nó da matriz; e se um nó está no índice n, seu primeiro filho na matriz está no índice 2n + 1 e seu próximo filho está no índice 2n + 2. Um heap tem certas operações que são realizadas na matriz.
Chrys
