BACHARELADO EM CIÊNCIAS DA COMPUTAÇÃO

[pic 1]

UNIVERSIDADE FEDERAL DO PARÁ

INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS

CURSO DE BACHARELADO EM CIÊNCIAS DA COMPUTAÇÃO

Projetos de Algoritmos II

UFPA

Belém,18 de Dezembro de 2013

Introdução

Um Heap de Fibonacci é uma estrutura de dados de proposta dual:

. Suporta um grupo de operações que constituem uma estrutura chamada de Heap mesclável.

. Algumas operações do Heap de Fibonacci são executadas em tempo amortizado constante, o que o torna adequado para aplicações que invocam estas operações constantemente.

Aplica-se bem, do ponto de vista teórico, em aplicações onde o número de EXTRACT-MIN e DELETE é pequeno em Relação às outras operações.

Aplicações: cálculo de árvores geradoras mínimas e busca por menores caminhos dada uma origem.
É um bom exemplo de estrutura de dados projetada com análise amortizada em mente.

Não foi projetada para dar um suporte eficiente a operação SEARCH.

Um Heap Mesclável é qualquer estrutura de dados que suporta as cinco seguintes operações, nas quais cada elemento tem uma chave:

Heap  Mesclável

1. MAKE-HEAP(), cria e retorno um heap vazio.

2. INSERT(H,X), insere o elemento x, cuja chave já tenha sido definida, no heap H.

3. MINIMUN(H), retorna um ponteiro para o elemento no heap H cuja chave é mínima.

4. EXTRACT-MIN(H), deleta o elemento do heap H cujoa chave é mínima, retornando um ponteiro para o elemento.

5. UNION(H1,H2), cria e retorno um heap que contem todos os elementos dos heaps H1 e H2. Os heaps h1 e H2 são destruídos nesta operação.

Um heap de Fibonacci é um heap mesclável que também suporta as duas operações:

1. DECREASE-KEY(H, x, k), assinala a um elemento x do heap H um nova valor k para sua chave, o qual ´e assumindo ser um valor não maior que o valor atual.1

2. DELETE(H, x), deleta o elemento x do heap H.

1Aqui será adotado o padrão como heap m´mínimo, sendo as operações de

MINUMUM, EXTRACT-MIN e DECREASE-KEY aplicáveis. Contudo também

seria possível definir um heap m´máximo, onde existiriam as funções MAXIMUM,

EXTRACT-MAX e INCREASE-KEY.

Prof. Tiago A. E. Ferreira Disciplina

Prof. Tiago A. E. Ferreira Disciplina de Projetos

• [pic 2]

Heap  de Fibonacci

• Os Heaps de Fibonacci, em teoria, são desejados quando a quantidade de chamadas das funções de EXTRACT-MIN e DELETE são mito menores que a quantidade de chamada das demais funções.

       

• Na prática, os fatores constantes e a complexidade de implementação faz os heaps de Fibonacci serem menos desejáveis do que os heaps binários para a maior parte das aplicações, exceto as aplicações com grandes montantes de dados.

• De forma geral, o interesse nos Heaps de Fibonacci são basicamente teóricos.

Estrutura

Um Heap de Fibonacci é um conjunto de árvores que são heaps mínimos. Cada árvore obedece a propriedade do heap mínimo:

• A chave de um dado nodo é maior ou igual da chave do seu pai.

[pic 3]

• Cada nodo x do heap de Fibonacci tem um ponteiro x.p para seu pai e um ponteiro x.child para cada um de seus filhos.
• Todos os filhos do nodo x são unidos por meio de uma lista.
• Circular e duplamente encadeada. Esta lista é uma chamada de lista de filhos de x.
• Cada filho y tem os ponteiros y.left e y.right que apontam para os seus irmãos da esquerda e direita respectivamente.

• Se o nodo y não tiver irmãos, então y.left = y.right = y.

• Os irmãos podem aparecer na lista de filhos em qualquer ordem.
• As listas circulares têm duas vantagens:

1. É armazenado o número de filhos da lista de filhos do nodo x em x.degree.
2. O Atributo de valor booleano x.mark indica se x tem perdido um filho desde da última vez que este tem sido filho de outro nodo.

• Os nodos criados são unmarked, e um nodo x se torna unmarked se este é feito filho de outro nodo.

• Um Heap de Fibonacci H é acessado por um ponteiro H.min para a raiz de uma árvore      contendo a menor chave.

• Este nodo é chamado de nodo mínimo do Heap de Fibonacci.

• As raízes de todas as  árvores são unidas por ponteiros left e right em um lista circular e duplamente encadeada, chamada lista de raízes do Heap de Fibonacci.
• Existe ainda o atributo H.n que armazena o número de nodos correntes no Heap H.

Método do Potencial – Análise Amortizada

Em linhas gerais, a análise de custo amortizada é uma análise media, onde se garante o desempenho médio de cada operação para o pior caso. Em particular, há o método do potencial:

• Neste método, o trabalho a ser realizar é considerado como energia potencial, ou simplesmente potencial, o qual pode ser liberado para pagar as operações futuras.
• O potencial é associado á estrutura como um todo.

Para um Heap de Fibonacci H, indica-se por t(H) o número de árvores na lista de Raízes de H e m(H) o número de nodos marcados em H.

É possível definir a função potencial (H) para o Heap H como,

                                     Φ(H) = t(H) + 2m(H)

• A função potencial para um conjunto de Heaps é a soma dos potenciais.
• É assumido que uma aplicação de um Heap de Fibonacci começa com um Heap vazio (sem heaps).

• Desta forma, a função potencial é zero.
• O potencial é sempre não negativo para todo tempo subsequente.

• Assuma que seja conhecido o limite superior D(n) sobre o grau máximo de qualquer nodo em um Heap de Fibonacci com n nodos.
• Quando apenas operações de mesclarem são suportadas, tem-se.

         

                               [pic 4]

• E quando s ao suportadas as funções DECREASE-KEY e DELETE,

                                    [pic 5]

Operações de Heap Mesclável

Várias operações em um Heap de Fibonacci desempenham um

“trade-off ”. Por exemplo,

• Inserção de um nodo adicionando-o a lista de raiz, o que toma um tempo constante.

• Começando com um heap vazio, e adicionando k nodos, tem-se uma lista de raiz com k nodos.
• O “trade-off ” ´e que se a função EXTRACT-MIN ´e invocada, apos a remoção no nodo apontado por H.min, há a necessidade de realizar uma busca pela menor chave nos k – 1 nodos restantes em H.

Criação

Para criar um Heap de Fibonacci vazio, a função MAKE-FIB-HEAP aloca e retorna um objeto tipo Heap de Fibonacci H, onde.

• H.n = 0
• H.min = NIL
• Não existem árvores em H
• Devido ao fato de t(H) = 0 e m(H) = 0, o potencial é Φ (H) = 0.
• Assim, o custo amortizado da função MAKE-FIB-HEAP é O(1)

Inserção

Assumindo que um dado nodo x já tenha sido alocado e que x.key já tenha sido preenchida, é possível inserir este nodo em um Heap de Fibonacci da seguinte forma,

...