Tutorial da estrutura de dados de heap

Dados são um conjunto de valores. Os dados podem ser coletados e colocados em uma linha, ou em uma coluna, ou em uma mesa ou na forma de uma árvore. A estrutura dos dados não é apenas a colocação de dados em qualquer um desses formulários. Na computação, a estrutura de dados é qualquer um desses formatos, além do relacionamento entre os valores, além das operações (funções) executadas nos valores. Você já deve ter conhecimento básico sobre a estrutura de dados de árvores antes de vir aqui, pois os conceitos ali serão usados ​​aqui com pouca ou nenhuma explicação. Se você não tiver esse conhecimento, leia o tutorial intitulado, Tutorial da estrutura de dados de árvores para iniciantes, no link, https: // linuxhint.com/árvore_data_structure_tutorial_beginners/. Depois disso, continue lendo este tutorial.Uma estrutura de dados de heap é uma árvore binária completa ou quase completa, onde o filho de cada nó é igual ou menor em valor do que o valor de seus pais. Como alternativa, é uma árvore em que o valor de um pai é igual ou menor que o valor de qualquer um de seus filhos. O valor (dado) de uma árvore também é chamado de chave.

Ilustração de estruturas de dados de heap

Existem dois tipos de montes: um max-heap e um min-heap. Uma estrutura max-heap é onde o valor máximo é a raiz e os valores se tornam menores à medida que a árvore é descendente; Qualquer pai é igual ou maior em valor do que qualquer um de seus filhos imediatos. Uma estrutura min-heap é onde o valor mínimo é a raiz e os valores se tornam maiores à medida que a árvore é descendente; Qualquer pai é igual ou menor em valor do que qualquer um de seus filhos imediatos. Nos diagramas a seguir, o primeiro é um max-heap e o segundo é um min-heap:

Para ambos. Uma linha em um nível na árvore não deve necessariamente ser preenchida do mínimo ao máximo, da esquerda; também não é necessariamente preenchido do máximo ao mínimo, da esquerda.

Representando uma pilha em uma matriz

Para o software usar uma pilha facilmente, o heap deve ser representado em uma matriz. O max-heap acima, representado em uma matriz é:

89, 85, 87, 84, 82, 79, 73, 80, 81 ,, 65, 69

Isso é feito começando com o valor 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ó estiver no índice (posição) n, seu primeiro filho na matriz está no índice 2n+1 e seu próximo filho estará 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 restante dos elementos na matriz.

Tal matriz, onde o significado de um elemento e a relação entre os elementos, está implícito na posição do elemento, é chamado de estrutura de dados implícita.

A estrutura de dados implícita para o Min-Heap acima é:

65, 68, 70, 73, 71, 83, 84 ,, 79, 80 ,, 85, 89

O max-heap 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 estará vazio na matriz.

Agora, se a pilha 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, 69

Nesta 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), além do relacionamento entre os valores, além das operações (funções) executadas nos valores. Para uma pilha, o relacionamento que passa por toda a pilha é que o pai deve ser igual ou maior em valor que as crianças, para um max-heap; e os pais devem ser iguais ou menos em valor que as crianças, por um min-heap. Este relacionamento é chamado de propriedade Heap. As operações de uma pilha são agrupadas sob os títulos da criação, básico, interno e inspeção. Segue -se um resumo das operações da pilha:

Resumo das operações de heap

Existem certas operações de software comuns com montes, como segue:

Criação de um monte

create_heap: criar uma pilha significa formar um objeto que representa a pilha. No idioma C, você pode criar uma pilha com o tipo de objeto de estrutura. Um dos membros da estrutura será a matriz de heap. O restante dos membros serão funções (operações) para a pilha. Create_heap significa criar uma pilha vazia.

Heapify: a matriz de heap é uma matriz parcialmente classificada (ordenada). Heapify significa, forneça uma matriz de heap de uma matriz não classificada - veja os detalhes abaixo.

Merge: Isso significa, forme uma pilha de união de dois montes diferentes - veja detalhes abaixo. Os dois heaps devem ser max-heap ou ambos. A nova pilha está em conformidade com a propriedade Heap, enquanto os montes originais são preservados (não apagados).

MELD: Isso significa que junte dois montes do mesmo tipo para formar um novo, mantendo duplicatas - veja os detalhes abaixo. A nova pilha está em conformidade com a propriedade Heap, enquanto os montes originais são destruídos (apagados). A principal diferença entre fusão e fusão é que, para a fusão, uma árvore se encaixa como uma subárvore na raiz da outra árvore, permitindo valores duplicados na nova árvore, enquanto para a fusão, uma nova árvore é formada, removendo duplicatas. Não há necessidade de manter os dois montes originais com a fusão.

Operações básicas de heap

find_max (find_min): localize o valor máximo na matriz Max-Heap e retorne uma cópia ou localize o valor mínimo na matriz min-heap e retorne uma cópia.

Inserir: Adicione um novo elemento à matriz de heap e reorganize a matriz para que a propriedade Heap do diagrama seja mantida.

Extract_max (Extract_min): localize o valor máximo na matriz Max-Heap, remova e retorne-o; ou localize o valor mínimo na matriz min-heap, remova e devolva-o.

Delete_max (delete_min): localize o nó raiz de um max-heap, que é o primeiro elemento da matriz Max-heap, remova-o sem necessariamente devolvê-lo; ou localize o nó raiz de um min-heap, que é o primeiro elemento da matriz min-heap, remova-o sem necessariamente devolvê-lo;

Substitua: localize o nó raiz de qualquer heap, remova -o e substitua -o por um novo. Não importa se a raiz antiga é devolvida.

Operações internas de heap

aumento_key (diminuição_key): Aumente o valor de qualquer nó para um max-heap e reorganizar para que a propriedade Heap seja mantida ou diminua o valor de qualquer nó para um min-heap e reorganizar para que a propriedade Heap seja mantida.

Exclua: Exclua qualquer nó e depois reorganize, para que a propriedade Heap seja mantida para o max-heap ou um min-heap.

shift_up: mova um nó para cima em um max-heap ou min-heap o tempo necessário, reorganizando para manter a propriedade Heap.

shift_down: mova um nó para baixo em um max-heap ou min-heap o tempo necessário, reorganizando para manter a propriedade Heap.

Inspeção de uma pilha

Tamanho: Isso retorna o número de chaves (valores) em um heap; não inclui os locais vazios da matriz de heap. Uma pilha pode ser representada por código, como no diagrama, ou com uma matriz.

está vazia: Isso retorna boolean verdade.

Peneirando em uma pilha

Existe peneirar e peneirar:

Peneirar: Isso significa trocar um nó com seus pais. Se a propriedade Heap não estiver satisfeita, troque o pai com seus próprios pais. Continue assim no caminho até que a propriedade Heap esteja satisfeita. O procedimento pode atingir a raiz.

Peneirar para baixo: Isso significa trocar um nó de grande valor com o menor de seus dois filhos (ou uma criança por uma pilha quase completa). Se a propriedade Heap não estiver satisfeita, troque o nó inferior com o nó menor de seus dois filhos. Continue assim no caminho até que a propriedade Heap esteja satisfeita. O procedimento pode atingir uma folha.

Pesando

Heapify significa classificar uma matriz não classificada para ter a propriedade Heap satisfeita para max-heap ou min-heap. Isso significa que pode haver alguns locais vazios na nova matriz. O algoritmo básico para intensificar um max-heap ou min-heap é o seguinte:

- Se o nó raiz for mais extremo do que qualquer um dos nó de seu filho, troque a raiz com o nó da criança menos extrema.

- Repita esta etapa com os nós das crianças em um esquema de travessia de árvore de pré-encomenda.

A árvore final é uma árvore de heap que satisfaz a propriedade Heap. Uma pilha pode ser representada como um diagrama de árvore ou em uma matriz. A pilha resultante é uma árvore parcialmente classificada, eu.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 detalhes de uma pilha

create_heap

Veja acima!

heapify

Veja acima

mesclar

Se as matrizes de heap,

89, 85, 87, 84, 82, 79, 73, 80, 81 ,, 65, 69

e

89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71

são mesclados, o resultado sem duplicatas pode ser,

89, 85, 87, 84, 82, 83, 81, 80, 79, 73, 68, 65, 69, 70, 71

Depois de peneirar. 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 árvores. Os dois montes 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 montes do mesmo tipo é o seguinte:

- Junte -se a uma matriz no fundo da outra matriz.

- Heapify está eliminando duplicatas, certificando -se de que nós, que não tinham filhos nos montes originais, ainda não têm filhos no novo Heap.

MELD

O algoritmo para fundir dois montes do mesmo tipo (dois max 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 o filho perdido da raiz do agora a subárvore extrema, para baixo na subárvore extrema.

A pilha resultante ainda está em conformidade com a propriedade Heap, enquanto os montes originais são destruídos (apagados). Os montes 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 Max-Heap e retornar uma cópia ou localizar o valor mínimo na matriz de mini-heap e devolver uma cópia. Uma matriz de heap por definição já satisfaz a propriedade Heap. Então, basta retornar uma cópia do primeiro elemento da matriz.

inserir

Isso significa que adicione um novo elemento à matriz de heap e reorganize a matriz para que a propriedade Heap do diagrama seja mantida (satisfeita). O algoritmo para fazer isso nos dois tipos de pilhas é o seguinte:

- Suponha 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 uma pilha completa é 1, ou 3, 7, 15 ou 31, etc.; Continue dobrando e adicionando 1.

- Coloque o nó na localização vazia mais adequada por magnitude, no final da pilha (no final da matriz de heap). Se não houver localização vazia, inicie uma nova linha do canto inferior esquerdo.

- Peneire se necessário, até que a propriedade Heap seja satisfeita.

Extract_max (Extract_min)

Localize o valor máximo na matriz Max-Heap, remova e retorne-o; ou localize o valor mínimo na matriz min-heap, remova e devolva-o. O algoritmo para extração_max (Extract_min) é o seguinte:

- Remova o nó raiz.

- Pegue (remova) o nó mais inferior direito (último nó na matriz) e coloque na raiz.

- Peneire conforme apropriado, até que a propriedade Heap seja satisfeita.

Delete_max (Delete_min)

Localize o nó raiz de um max-heap, que é o primeiro elemento da matriz max-heap, remova-o sem necessariamente devolvê-lo; ou localize o nó raiz de um min-heap, que é o primeiro elemento da matriz min-heap, remova-o sem necessariamente devolvê-lo. O algoritmo para excluir o nó raiz é o seguinte:

- Remova o nó raiz.

- Pegue (remova) o nó mais inferior direito (último nó na matriz) e coloque na raiz.

- Peneire conforme apropriado, até que a propriedade 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 é devolvida. Peneire se apropriado, até que a propriedade Heap seja satisfeita.

Operações internas de heap

aumento_key (diminuição_key)

Aumente o valor de qualquer nó para um max-heap e reorganizar para que a propriedade Heap seja mantida ou diminua o valor de qualquer nó para uma mina e reorganizar para que a propriedade Heap seja mantida. Peneirar para cima ou para baixo conforme apropriado, até que a propriedade Heap seja satisfeita.

excluir

Remova o nó de interesse e depois reorganize, para que a propriedade Heap seja mantida para o max-heap ou um min-heap. O algoritmo para excluir um nó é o seguinte:

- Remova o nó de interesse.

- Tome (remova) o nó mais baixo do lado direito (último nó na matriz) e coloque no índice do nó removido. Se o nó excluído estiver na última fila, então isso pode não ser necessário.

- Peneirar para cima ou para baixo conforme apropriado, até que a propriedade Heap seja satisfeita.

shift_up

Mova um nó para cima em um max-heap ou min-heap o tempo necessário, reorganizando para manter a propriedade Heap-peneire.

shift_down

Mova um nó para baixo em um max-heap ou min-heap o tempo necessário, reorganizando para manter a propriedade Heap-peneire para baixo.

Inspeção de uma pilha

tamanho

Veja acima!

está vazia

Veja acima!

Outras classes de pilhas

A pilha descrita neste artigo pode ser considerada como a principal (geral) heap. Existem outras classes de pilhas. No entanto, os dois que você deve saber além disso são a pilha binária e a pilha D-ERY.

Heap binário

A pilha binária é semelhante a essa pilha 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 cheia.

Heap D-Ear

Uma pilha binária é uma pilha de 2 anos. Uma pilha em que cada nó tem 3 filhos é uma pilha de 3 anos. Uma pilha em que cada nó tem 4 filhos é uma pilha de 4 anos, e assim por diante. Um heap d-yar tem outras restrições.

Conclusão

Uma pilha é uma árvore binária completa ou quase completa, que satisfaz a propriedade Heap. A propriedade Heap possui 2 alternativas: para um max-heap, um pai deve ser igual ou maior em valor do que os filhos imediatos; Para um min-heap, um pai deve ser igual ou menos em valor do que os filhos imediatos. Uma pilha pode ser representada como uma árvore ou em uma matriz. Quando representado em uma matriz, o nó raiz é o primeiro nó da matriz; E se um nó estiver no índice n, seu primeiro filho na matriz está no índice 2n+1 e seu próximo filho está no índice 2n+2. Uma pilha tem certas operações que são executadas na matriz.

Chrys