DEV Community

Alex Reis
Alex Reis

Posted on

Estruturas de Dados: Heap

#programming #dsa #braziliandevs #beginners

Heap é uma lista linear onde cada elemento armazena um dado e sua prioridade de modo que:

  • H[i] > H[2i], (ou H[i] < H[i/2])
  • H[i] > H[2i+1], Para 1 <= i <= n.

Exemplo: [33, 32, 38, 31, 29, 26, 25, 30, 27]

Essa estrutra pode ser representada visualmente na forma de uma árvore binaria, onde cada nó possui prioridade maior que seus dois filhos, se existirem. Na memória a estrutra está disposta como uma lista linear sequencial.

As condições anteriormente descritas implicam que o elemento de maior prioridade sempre é o primeiro, ou seja, a raiz da árvore.

  • seleção: O(1)
  • inserção: O(log n)
  • remoção: O(log n)
  • alteração: O(log n)
  • construção: O(n)

Alteração de prioridade

De modo geral, uma operação que se deseja realizar no heap está associada a "subir" ou "descer" num caminho da árvore. Associa-se então o aumento de prioridade à "subida" e a diminuição à "descida". OS algoritmos correspondentes a estas operações são:

Algoritmo subir() recursivo

 subir(i) j := i/2 se j >= 1 então se H[j].chave < H[i].chave então torcar (H[j], H[i]) subir(j)
Enter fullscreen mode Exit fullscreen mode

Algoritmo subir() iterativo

 subir(i) j := i/2 enquanto j >= 1 e H[j].chave < H[i].chave torcar H[j] <=> H[i] i := j j := i/2
Enter fullscreen mode Exit fullscreen mode

Algoritmo descer() recursivo

 descer(i,n) j := 2*i se j <= n então se j < n então se H[j].chave < H[j+1].chave então j := j+1 se H[i].chave < H[j].chave então trocar (H[i], H[j]) descer(j,n)
Enter fullscreen mode Exit fullscreen mode

Algoritmo descer() iterativo

 descer(i,n) j := 2*i enquanto j <= n faça se j < n então se H[j].chave < H[j+1].chave então j := j+1 se H[i].chave < H[j].chave então trocar (H[i], H[j]) i := j j := 2*i senão j := n+1
Enter fullscreen mode Exit fullscreen mode

As complexidades dos algoritmos subir() e descer() recursivos são as mesmas de percorrer o caminho de uma árvore binária completa: O(log n)

Inserção de elemento

Suponha a inserção de um novo elemento, a lista agora passará a ter n+1 elementos. Obviamente o lista não respeita mais a propriedade de heap. O procedimento a seguir corrige esse problema.

 inserir(x) H[n+1] := x n := n+1 subir(n)
Enter fullscreen mode Exit fullscreen mode

Complexidade igual ao algoritmo subir(): O(log n)

Remoção de elemento

A remoção é feita sempre com o de maior prioridade, logo a sua posição fica vazia e a lista passa a ter n-1 elementos, o último elemento então deve preenche-la mas como sua prioridade está deslocada a lista deve ser corrigida.

 remover() se n != 0 então H[1] := H[n] n := n-1 descer(1, n) senão "lista vazia"
Enter fullscreen mode Exit fullscreen mode

A complexidade desse algoritmo depende do algoritmo descer(): O(log n)

Construção de um heap

Observando que toda lista ordenada corresponde a um heap, podemos construir um através da ordenação de uma lista.

 construirHeap() para i := 2 até n faça subir(i)
Enter fullscreen mode Exit fullscreen mode

Complexidade O(n log n)

Uma solução alternativa é descrita observando que para um nó sem filhos satisfaz as propriedades de heap, isto é, todo nó alocado a partir da posição n/2 + 1. Por essa razão, na construção de um heap os únicos nós relevantes são os internos da árvore. Estes devem ter suas prioridades verificadas e acertadas.

 construirHeapOtimizado() para i := n/2 até 1 faça descer(i,n)
Enter fullscreen mode Exit fullscreen mode

Complexidade linear: O(n)

Referência

Livro: Estruturas de Dados e seus Algoritmos

Top comments (0)