24

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

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.176

Passo 1 de 5keyboard_arrow_downkeyboard_arrow_up

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. No heap de Fibonacci há dois campos em cada nó: marcado e não marcado. No começo todos os nós do heap são não marcados, mas se um nó perder seus filhos então o pai do nó correspondente é marcado.

Passo 2 de 5keyboard_arrow_downkeyboard_arrow_up

Para que x se torne uma raiz marcada, considera-se que os nós estão inicialmente não marcados, e considera-se a propriedade de que o nó pai deve ter valor menor do que o filho.

Passo 3 de 5keyboard_arrow_downkeyboard_arrow_up

Assim, força-se que um dos filhos tenha valor maior do que o nó pai, devendo retirá-lo da sua posição e movê-lo para um nó pai de menor valor. O nó pai antigo é então marcado.

Passo 4 de 5keyboard_arrow_downkeyboard_arrow_up

Utilizando o corte por cascata, nota-se que x chega à linha do nó raiz, não podendo ser cortado e, assim, permanecendo raiz marcada.

Passo 5 de 5keyboard_arrow_downkeyboard_arrow_up

Se x já está marcado, ele pode continuar marcado, pois não pode ser retirado da lista de raiz. Da mesma forma, se x não está marcado, não é possível marcar os pais por são nós raiz. Assim, não importa se x está marcado ou não inicialmente.

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.