Heap de Fibonacci
Alberto Rodrigues Costa Junior - (arcj)
Roteiro
• Introdução
• Estrutura
• Operações
• MAKE-HEAP
• INSERT
• MINIMUM
• UNION
• EXTRACT-MIN
• DECREASE-KEY
• DELETE
• Limite do grau máximo
Introdução
• Fredman e Tarjan em (Desenvolvido) 1984
/ (Publicado)1987.
• Aplicações em problemas de Menor
caminho, AGPM ...
Introdução
• Heaps binomiais suportam operações
Minimum, Extract Minimum, Union, Delete e
Decrease Key em tempo O(lgn) no pior caso.
• Heaps de Fibonacci suportam as mesmas
operações acima que não envolvem exclusão
em tempo amortizado O(1).
Introdução
Introdução
• Não foi desenvolvido para dar suporte eficiente
a operação de Search.
• Do ponto de vista prático, os fatores constantes
e a complexidade a tornam pouco desejável
para a maioria dos problemas.
Estrutura
• Semelhante ao HB, mas tem uma estrutura
bem menos rígida.
• HB: Consolida árvores depois de cada Insert.
• HF: Adia a consolidação até a próxima
exclusão
Estrutura
• Como HB, o HF é uma coleção de árvores.
• Também é coleção de heaps mínimos.
Estrutura
• Lista de raízes (circular e duplamente ligada).
• Ponteiro Min[H] apontado pra raiz que tiver menor valor.
• Cada nó x tem um ponteiro p[x] pro seu pai. E um ponteiro
child[x] pra um de seus filhos.
• Cada filho y esta em lista duplamente ligada e circular(left[y]
e right[y]).
Estrutura
• degree[x] - número de filhos de x.
• mark[x] - indica se o nó x perdeu um filho desde a ultima vez
que se tornou filho de outro nó.
• n[H] - número de nós em H.
Função Potencial
• Usada para analisar o desempenho de
operações de HF.
• t(H) o número de árvores.
• m(H) o número de nós marcados.
φ(H) = t(H) + 2m(H)
Operações
• Operações de heaps intercaláveis
• Make Heap
• Insert
• Minimum
• Union
• Extract Min
Operações
• Árvores Binomiais Não Ordenadas
• Uma árvore binomial não ordenada é
como uma arvore binomial:
• U0 consiste de apenas um nó
• Uk consiste de duas árvores binomiais não
ordenadas Uk-1, onde a raiz de uma delas
se torna filho da outra
Operações
• Propriedades de árvores binomiais não
ordenadas
• Para uma árvore binomial não ordenada U
vale:
• Há 2^k nós em Uk.
• A altura é k.
• Há exatamente
nós de profundidade i
para i = 0 ,1,...,k
• A raiz tem grau k, que é o maior grau de
qualquer outro nó. Os filhos da raiz são
raízes de árvores U0,U1, . . . Uk−1
emqualquer ordem
Operações
• Grau Máximo
• D(n) é o grau máximo de qualquer nó em um HF
com n nós
• Logo, se o HF é uma coleção de árvores binomiais
não ordenadas, então D(n) = lgn.
Make-Heap
Make-Heap()
1) n[H] = 0
2) min[H] = NIL
3) Retorna H
• t(H) = 0
• m(H) = 0
• Então φ(H) = 0+ 2*0 = 0
• Custo amortizado é igual ao custo real O(1)
Insert
Insert
Insert
• Seja H o heap de entrada e H’ heap resultante
t(H’) = t(H) + 1 e m(H’) = m(H) então o aumento
do potencial é :
((t(H) + 1) + 2m(H)) – (t(H) + 2m(H)) = 1
Como o custo real é O (1), o custo amortizado é (1) + 1 = Θ (1)
Minimum
• O nó mínimo é dado pelo ponteiro min[H].
Tempo real O(1) e tendo em vista que o
potencial não muda o custo amortizado desta
operação é igual ao seu custo real.
Union
Union
• Mudança de potencial:
φ(H) = φ(H1) + φ(H2)
= (t(H) + 2m(H)) - ((t(H1) + 2m(H1)) + (t(H2) + 2m(H2)) )
=0
Desse modo o custo amortizado de Union é
igual ao custo real Θ(1).
Extract-min
• O processo de extrair o nó minimo é mais complicado.
• Onde a consolidação das árvores finalmente ocorre.
Extract-min
Extract-min
Extract-min
Extract-min
• O(D(n)+ t(H)) + ((D(n)+1) + 2m(H)) – (t(H) +2m(H))
= O(D(n)) + O(t(h)) – t(h)
= O(D(n))
Decrease-key
• Aqui mostramos como a redução de uma chave de um
nó em um HF pode ser realizada com custo amortizado
O(1).
• Mais adiante, mostraremos que a deleção de um nó
pode ser executada em tempo amortizado O(D(n)).
• Essas operações não preservam a propriedade de que
todas as árvores no HF são árvores binomiais não
ordenadas.
• Estas árvores são “próximas” o suficiente para se limitar
o grau máximo D(n) por o(lgn).
Decrease-key
Decrease-key
Decrease-key
Decrease-key
Delete
Limitando o grau Máximo
• Para mostrar que a análise amortizada de Extract-Min e Delete
executam em tempo amortizado O(lgn), temos que mostrar
que D(n) (grau máximo de um nó em heap com n chaves) é da
ordem O(lgn).
• Se todas as árvores são árvores binomiais não ordenadas, então
D(n) = floor(lg(n)).
• Os cortes que ocorrem em Decrease Key, entretanto, podem fazer
com que as árvores do HF deixem de ser binomiais
• Mostrar que, em virtude de cortarmos um nó x do seu pai y
sempre que ele perde dois filhos, teremos D(n) é O(lgn)
Limitando o grau Máximo
• Para cada nó x de um HF, defina size(x) como o número de
nós, incluindo x, que pertencem à árvore com raiz em x.
• Vamos mostrar que size(x) é exponencial em degree[x].
• Lema
• Seja x um nó de um HF e suponha que degree[x] = k.
• Sejam y1, y2, . . . , yk os filhos de x na ordem que eles foram ligados
a x, a partir do primeiro ao último (mais recente).
• Então, degree[y1] >= 0 e degree[yi ]>= i −2, para i = 2, 3, . . . , k
Limitando o grau Máximo
• Prova
• Obviamente, degree[y1] >= 0.
• Para i >= 2, quando yi se tornou filho de x os
elementos y1, . . . , yi−1 eram filhos de x, logo
devemos ter degree[x] = i − 1.
• Note que yi é ligado a x apenas se degree[x] =
degree[yi ], portanto devemos ter degree[yi ] = i − 1
no momento da ligação.
• Dai concluímos que degree[yi ] >= i − 2.
Limitando o grau Máximo
• Finalmente atingimos a parte da análise que explica o nome
“Heap de Fibonacci”.
• Lembramos que a série Fibonacci é definida por:
• Lema:
Limitando o grau Máximo
• Prova por indução
caso base k = 0
= 1 + F0
=1+0
= 1 = F2
Limitando o grau Máximo
• Hipótese indutiva que Fk +1 = 1+
• F2 + k = Fk +1 + Fk +1
= Fk +(1 +
=1+
𝑘−1
𝑖=0 𝐹𝑖
𝑘
𝑖=0 𝐹𝑖
)
𝑘−1
𝑖=0 𝐹𝑖
Limitando o grau Máximo
• Lema:
Limitando o grau Máximo
Limitando o grau Máximo
• Lema:
• Seja x um nó de um HF
• Seja k = degree[x] o grau de x.
• Então
• Prova
• Sk é o menor valor possível size(x) de todos os nós z tais que
degree[z] = k
• Sk é no máximo size(x), e o valor de sk aumenta monotonicamente
com k
Limitando o grau Máximo
Limitando o grau Máximo
Limitando o grau Máximo
• Corolário: