TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

BACHARELADO EM CIÊNCIAS DA COMPUTAÇÃO

Por:   •  29/1/2019  •  Trabalho acadêmico  •  2.471 Palavras (10 Páginas)  •  110 Visualizações

Página 1 de 10

[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,

...

Baixar como (para membros premium)  txt (12.6 Kb)   pdf (844.1 Kb)   docx (1 Mb)  
Continuar por mais 9 páginas »
Disponível apenas no TrabalhosGratuitos.com