64
Algoritmos - Teoria e Prática - 3ª Ed. 2012

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

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

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.

Navegar por capítulo