Estruturas de dados heap

Heap é um caso especial de estrutura de dados de árvore binária balanceada em que a chave do nó raiz é comparada com seus filhos e organizada de acordo. E seα tem nodo filho β então -

chave (α) ≥ chave (β)

Como o valor de parent é maior que o de child, esta propriedade gera Max Heap. Com base nesses critérios, um heap pode ser de dois tipos -

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap - Onde o valor do nó raiz é menor ou igual a qualquer um de seus filhos.

Max-Heap - Onde o valor do nó raiz é maior ou igual a qualquer um de seus filhos.

Ambas as árvores são construídas usando a mesma entrada e ordem de chegada.

Algoritmo de construção de pilha máxima

Devemos usar o mesmo exemplo para demonstrar como um Max Heap é criado. O procedimento para criar Min Heap é semelhante, mas optamos por valores mínimos em vez de valores máximos.

Vamos derivar um algoritmo para o heap máximo inserindo um elemento por vez. A qualquer momento, o heap deve manter sua propriedade. Durante a inserção, também assumimos que estamos inserindo um nó em uma árvore já montada.

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Note - No algoritmo de construção Min Heap, esperamos que o valor do nó pai seja menor que o do nó filho.

Vamos entender a construção de Max Heap por uma ilustração animada. Consideramos a mesma amostra de entrada que usamos anteriormente.

Algoritmo de exclusão de heap máximo

Vamos derivar um algoritmo para excluir do heap máximo. A exclusão no heap máximo (ou mínimo) sempre ocorre na raiz para remover o valor máximo (ou mínimo).

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.