30

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 3

719463-19.2-1E AID: 40 | 01/08/2016

O heap Fibonacci é um tipo de estrutura de dados na qual os heaps são organizados na forma de uma coleção de árvores enraizadas ordenadas por heap de mínimo, ou seja, em cada árvore a chave de um nó é maior ou igual à chave de seu pai. Na qual a árvore com o valor de chave mínimo é o nó raiz no heap Fibonacci, e os filhos são conectados ou organizados em uma lista circular duplamente ligada.

Para resolver o problema em questão, é utilizado o algoritmo FIB-HEAP-EXTRACT-MIN que foi implementado na sessão 19.2 Extraindo o nó mínimo. A função em questão, como o nome diz, extrai o nó com o menor valor da árvore. No algoritmo implementado, o nó que aponta para o mínimo é extraído e seus filhos são juntados na raiz, após isso a função CONSOLIDATE é chamada para reorganizar a árvore no formato heap.

Tendo conhecimento do algoritmo citado, ele será utilizado para extrair o valor mínimo da árvore referenciada na figura 19.4(m). Seguindo passo a passo a implementação temos que inicialmente z recebe o valor mínimo de H, que nesse caso é 7.

Como z contém um valor, um loop vai percorrer cada filho de z = 7 e adicionar cada um deles a lista raiz e setar seus pais como NIL. Assim, a figura 19.4(m) se torna como a figura abaixo.

Com o nó que contém o valor 7 isolado, pode-se então remover z = 7 da lista raiz e então setar o novo valor mínimo o próximo elemento da lista, no caso, H.min = 18.

Feito isso, é chamado o procedimento CONSOLIDATE no heap, para que possa balancear e reorganizar no formato correto. Um array armazenará os graus de cada nó setando todos como NIL e considerando cada nó da lista raiz um por um e então reorganizará a árvore de forma que obedeça o heap Fibonacci. Após concluido o CONSOLIDATE a árvore estará no formato correto e o valor mínimo terá sido atualizado para o novo menor valor após a remoção do 7.

Portanto, após a remoção do valor mínimo 7 e a atualização da árvore e do novo valor mínimo, o heap Fibonacci assumira a seguinte forma:

lock Ver solução completa

Navegar por capítulo

O passo a passo dos exercícios mais difíceis

12xR$ 29,90 /mêsCancele quando quiser, sem multa

E mais

  • check Videoaulas objetivas
  • check Resumos por tópicos
  • check Salve para ver depois
  • check Disciplinas ilimitadas
  • check Filtros exclusivos de busca