Cátia Vaz
Amontoados Relaxados e Filas com Prioridade
9 de Setembro de 2009
ISEL, Instituto Politécnico de Lisboa
Conteúdo
1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Estado da Arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Amontoados Relaxados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Árvores Binomiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Amontoados Relaxados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Rank Relaxed Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Run Relaxed Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Detalhes de Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3
Filas com Prioridade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1 Tipo de Dados Abstracto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 Detalhes de Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4
Avaliação Experimental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1 Sequências de Números Aleatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5
Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
A Implementação em Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1 Rank Relaxed Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 Run Relaxed Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.3 Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
3
55
55
77
107
Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
1
Introdução
O problema de gerir uma fila de elementos com prioridade surge frequentemente no desenvolvimento de algoritmos para resolver problemas em engenharia informática e, na maior
parte dos casos, tem um impacto significativo na eficiência da solução implementada. Dado
um conjunto de elementos x cuja prioridade é definida por uma chave k(x), uma fila com
prioridade é um tipo de dados abstracto que suporta as seguintes operações:
insert(x), que insere o elemento x na fila;
removeMin(), que retorna e remove o elemento de menor chave na fila;
minimum(), que retorna o elemento de menor chave na fila sem o remover.
Neste caso o elemento com menor chave terá maior prioridade. Alternativamente, pode-se
definir fila com prioridade como um tipo de dados abstracto com as operações removeMax, que retorna e remove o elemento de maior chave na fila, e maximum, que retorna
o elemento de maior chave na fila mas sem o remover. Contudo a escolha entre as duas
definições está directamente relacionada com a ordem total imposta aos elementos. Logo,
sem perda de generalidade, neste trabalho adopta-se a primeira definição, i.e., o elemento
com a menor chave tem maior prioridade. Na solução de alguns problemas é necessário que
o tipo de dados abstracto fila com prioridade suporte a operação:
decreaseKey(x, v), que atribui a chave v < k(x) ao elemento x, i.e., k(x) = v.
Embora estas sejam as operações básicas, este tipo de dados abstracto pode incluir outras operações como a operação remove, que remove um dado elemento da fila, ou a
operação meld, que funde duas filas com prioridade. Caso a operação remove seja suportada, a operação decreaseKey pode ser definida através da operação remove seguida
da operação insert. Contudo esta não é a prática usual por razões de eficiência.
Em engenharia informática as filas com prioridade são utilizadas na solução de vários
problemas, e.g., na determinação de caminhos mais curtos em grafos [1], na determinação
de árvores abrangentes de menor custo [2] e no escalonamento de processos e tarefas em
1 Introdução
2
sistemas operativos [3]. Muitos destes problemas surgem no contexto de sistemas de alta
performance e em tempo real, onde a eficiência da implementação das filas com prioridade
é determinante. Em geral a implementação varia bastante com o problema em estudo.
Por exemplo, no escalonamento de processos e tarefas em sistemas operativos, as chaves
tomam valor num conjunto de valores finito. Neste caso, dado que a dimensão do conjunto
domı́nio é apenas de algumas dezenas, a implementação mais simples passa por associar
uma lista de elementos a cada chave e todas as operações podem ser implementadas com
tempo O(1). Porém, quer para o problema de determinar os caminhos mais curtos, quer
para o problema de determinar a árvore abrangente de menor custo, esta abordagem não
é em geral viável dada a dimensão do domı́nio e a natureza das chaves. Neste caso a
implementação mais simples será utilizar uma lista em que os elementos são guardados
por ordem arbitrária ou uma lista em que os elementos são ordenados pelo valor da chave.
Contudo estas abordagens implicam que a operação removeMin, no primeiro caso, e a
operação insert, no segundo caso, corram em tempo Ω(n) com n o número de elementos
na fila. Embora outras implementações sejam possı́veis, nas últimas três décadas foram
publicados vários resultados que apontam os amontoados como a estrutura de dados mais
adequada para a implementação de filas com prioridade. De um modo geral um amontoado
é uma árvore em que cada nó tem uma chave associada e todos os descendentes tem
chaves de valor superior. Nos trabalhos publicados foram apresentadas diversas estruturas
de dados e vários resultados teóricos a respeito dos tempos de execução das operações
descritas. Contudo nem todas as estruturas de dados são viáveis para implementar na
prática, conduzindo muitas vezes a piores resultados que estruturas de dados teoricamente
menos eficientes.
O objectivo deste estudo é analisar a viabilidade prática das estruturas de dados
avançadas para implementar amontoados e, consequentemente, filas com prioridade. A
motivação para este estudo prende-se com a utilidade prática destas estruturas de dados
no desenvolvimento de inúmeros algoritmos e com o interesse pedagógico em ensiná-las
em disciplinas avançados de engenharia informática. As contribuições deste estudo são: a
implementação das várias estruturas de dados discutidas e a sua avaliação experimental;
a implementação do tipo de dados abstracto fila com prioridades permitindo a utilização
das várias estruturas de dados; a discussão do interesse pedagógico e viabilidade prática
da inclusão destas implementações em bibliotecas de uso geral.
1.1 Estado da Arte
3
1.1 Estado da Arte
A concretização mais simples de amontoados foi introduzida por Williams [4], conhecidos por amontoados binários. Uma fila com prioridade implementada sobre amontoados
binários permite consultar o mı́nimo em tempo O(1) no pior caso e extrair o mı́nimo, inserir e remover elementos em tempo O(log n) no pior caso. Os amontoados binários, ainda
que teoricamente não constituam a estrutura de dados mais eficiente, são os mais utilizados nas implementações de filas com prioridade disponı́veis nas diversas bibliotecas. Este
facto deve-se à simplicidade de implementação e a ser possı́vel implementar amontoados
binários sobre vectores recorrendo apenas à indexação, conduzindo a uma menor utilização
de memória. Dado o tempo de execução das operações e os baixos requisitos de memória,
os amontoados binários são em geral apropriados para aplicações que tenham de manipular
grandes quantidades de dados.
Nos últimos anos foram propostas novas concretizações de amontoados com vista a melhorar o tempo de execução das várias operações e que contribuı́ram para implementações
eficientes de vários algoritmos, como por exemplo os algoritmos de Dijkstra [1] e de Prim [2].
Na sua grande maioria as estruturas de dados propostas suportam a operação meld, i.e.,
amontoados fundı́veis [5]. O principal objectivo consiste em (1) reduzir o tempo de execução
de todas as operações para O(1) no pior caso, excepto as operações removeMin e remove
que devem ter tempo de execução O(log n) no pior caso. A razão deste objectivo prende-se
com o facto que na maioria dos casos o número de inserções e de diminuições do valor das
chaves é superior ao número de remoções. Um exemplo é o algoritmo de Dijkstra [1] em
que o número de actualizações é proporcional ao número de arcos m no grafo e o número
de extracções é proporcional ao número de vértices n. Como o número de arcos é regra
geral maior que o número de vértices, uma estrutura de dados que satisfaça (1) conduz a
um tempo de execução do algoritmo O(n log n + m) no pior caso.
Os amontoados binomiais foram propostos por Vuillemin [6] e suportam todas as
operações em tempo O(log n) no pior caso, incluindo a operação meld que nos amontoados binários leva tempo O(n). Com base nos amontoados binomiais foram propostas
várias estruturas de dados que exploram versões relaxadas. Fredman and Tarjan [7, 8] propuseram os amontoados de Fibonacci, uma relaxação dos amontoados binomiais em que
se permite que as árvores binomiais não sejam completas. Os amontoados de Fibonacci
suportam as operação de remoção e de extracção do mı́nimo em tempo O(log n) amortizado e todas as outras operações, em particular a actualização de chaves, em tempo O(1)
amortizado [9]. Desta forma, os amontoados de Fibonacci permitiram melhorar a comple-
1.1 Estado da Arte
4
xidade assimptótica de vários algoritmos, em particular dos algoritmos de Dijkstra [1] e
de Prim [2] para um tempo de execução O(n log n + m) no pior caso. Contudo, dada a
complexidade da estrutura de dados e os requisitos de memória, na prática os amontoados
de Fibonacci não provaram ser eficientes, conseguindo-se regra geral melhores resultados
com os amontoados binários.
Os amontoados emparelhados (pairing heaps) [10] foram introduzidos como uma alternativa aos amontoados de Fibonacci. Esta estrutura de dados garante para todas as operações
tempo O(log n) amortizado e, conjecturava-se, tempo O(1) amortizado para a operação decreaseKey. No entanto em trabalhos posteriores provou-se que o tempo amortizado para
√
a operação decreaseKey é O(22 log log n ) [11], verificando-se ainda Ω(log log n) [12]. Recentemente, Elmasry [13] introduziu uma variante de amontoados emparelhados com um
tempo O(log log n) amortizado para a operação decreaseKey. A vantagem em relação
aos amontoados de Fibonacci reside no facto de serem mais competitivos na prática. Driscoll et al. [14] propuseram duas estruturas de dados, rank relaxed heaps e run relaxed
heaps, ambas com base nos amontoados binomiais. Tal como os amontoados de Fibonacci,
a técnica consiste em relaxar os amontoados binomiais. Porém neste caso as árvores binomiais são completas e a relaxação verifica-se ao nı́vel da propriedade dos amontoados, i.e., um
número limitado de nós pode ter uma chave menor que o seu pai. Os rank relaxed heaps têm
a mesma complexidade assimptótica amortizada que os amontoados de Fibonacci. Os run
relaxed heaps suportam as operações remove, removeMin e meld em tempo O(log n)
no pior caso e todas as outras operações em tempo O(1) no pior caso. Brodal [15] obteve
ainda uma estrutura de dados que suporta as operações de remoção em tempo O(log n)
no pior caso e todas as outras operações em tempo O(1) no pior caso. No entanto é uma
estrutura de dados bastante complexa quando comparada com os amontoados relaxados
propostos por Driscoll et al.. Com vista a melhorar os tempos de execução das operações
dos amontoados relaxados, nomeadamente o número de comparações, Elmasry et al. apresentou recentemente uma nova estrutura, two-tier relaxed heaps, composta por dois run
relaxed heaps [16].
Na última década, o foco tem sido a melhoria das estruturas de dados de modo a
conseguir-se na prática implementações competitivas, continuando a garantir os limites
assimptóticos teóricos para o tempo de execução das operações [17, 18, 19, 20]. Os principais
objectivos são reduzir o número instruções para cada operação, em particular o número de
comparações [21], e reduzir os requisitos de memória.
1.1 Estado da Arte
5
Ainda que se tenham verificado todos estes esforços para obter implementações eficientes de filas com prioridade, a maior parte das bibliotecas disponı́veis não implementam
nenhuma destas estruturas mais avançadas. No que respeita à implementação do tipo de
dados abstracto fila com prioridades, a maior parte das implementações não suporta a
operação decreaseKey directamente e são baseadas em amontoados binários. É claro
que é possı́vel implementar um fila de prioridades sobre o tipo de dados abstracto mapa
ordenado disponibilizado em quase todas as bibliotecas e que, regra geral, é implementado
sobre árvores binárias de pesquisa balanceadas ou sobre amontoados binários. Em ambos
os casos o custo das operações insert, removeMin e decreaseKey é O(log n), não garantindo os limites assimptóticos das estruturas de dados mais avançadas para as operações
insert e decreaseKey.
2
Amontoados Relaxados
Os amontoados relaxados foram propostos por Driscoll et al. [14] como uma alternativa
aos amontoados de Fibonacci [8]. Quer os amontoados relaxados quer os amontoados de
Fibonacci são baseados em amontoados binomiais e, com vista a melhorar o tempo de
execução das operações, introduzem relaxações ao nı́vel das árvores binomiais. A principal diferença entre ambos reside precisamente na forma como são feitas as relaxações.
Enquanto que os amontoados de Fibonacci introduzem relaxações ao nı́vel da estrutura
das árvores binomiais, os amontoados relaxados consideram árvores binomiais completas
e introduzem relaxações ao nı́vel da ordem dos nós. Esta última abordagem, para além de
permitir implementações mais eficientes na prática, permite concretizar as operações remove, removeMin e meld em tempo O(log n) no pior caso e todas as outras operações
em tempo O(1) no pior caso também, em particular a operação decreaseKey. Driscoll
et al. propuseram duas estruturas de dados, rank relaxed heaps e run relaxed heaps. Ambas
as estruturas de dados garantem os tempos anteriores para a execução das operações, contudo no primeiro caso os tempos são amortizados tal como acontece com os amontoados
de Fibonacci.
No que se segue apresentam-se e discutem-se em detalhe ambas as concretizações de
amontoados relaxados. Antes é no entanto necessário introduzir árvores binomiais e alguma
notação.
2.1 Árvores Binomiais
Antes de definir árvore binomial é necessário rever alguns conceitos relativos a árvores em
geral. Uma árvore é um grafo ligado, não dirigido e acı́clico, i.e., um par (V, E) com V o
conjunto de vértices ou nós e E ⊆ V × V o conjunto de arcos tal que existe um e um só
2.1 Árvores Binomiais
x
8
1
y
30
10
5
15
22
8
Br
25
15
11
13
22
21
Br
27
16
36
Figura 2.1. À esquerda, construção de uma árvore binomial Br+1 a partir de duas árvores binomiais Br . À direita,
exemplo de uma árvore binomial B4 , i.e., com grau 4.
caminho (constituı́do por vértices distintos) entre cada par de vértices. Uma árvore com
raiz é uma árvore em que um vértice, designado por raiz, é distinguido dos outros.
Considere-se uma árvore com raiz. Dado x um nó da árvore, designa-se por ascendente
de x qualquer nó y que se encontre no caminho entre o nó x e a raiz r. Neste caso x é
também um descendente de y. Dado um nó y e um nó x descendente de y e adjacente a y,
x diz-se filho de y e y pai de x. Note-se que a raiz é o único nó sem pai. Dado um nó x, a
sub-árvore de raiz x é a árvore induzida pelos descendentes de x, com raiz x.
Um nó designa-se por folha ou terminal se não tiver descendentes, caso contrário designase por nó interno ou não terminal. Qualquer nó não terminal distinto da raiz pode também
designar-se por nó intermédio. O grau ou rank de um nó é igual ao seu número de filhos e
uma árvore diz-se n-ária se tiver pelo menos um nó de grau n.
Dada uma árvore com raiz, define-se o nı́vel para cada nó e a altura da árvore. Um nó x
diz-se estar no nı́vel n se o caminho entre a raiz r e o nó x tiver n arcos. Uma árvore tem
altura h se o máximo dos nı́veis das suas folhas for h.
Dada uma ordem total para os nós, uma árvore com raiz diz-se ordenada se os filhos de
cada nó estiverem ordenados. Neste caso, se x tiver grau n, os seus filhos são identificados
por primeiro filho, segundo filho, ..., n-ésimo filho. Neste documento o n-ésimo filho é
também designado por último filho do nó x.
As árvores binomiais definem-se recursivamente como se segue: a árvore binomial B0
consiste num único nó, a sua raiz; a árvore binomial Br+1 é composta por duas árvores
binomiais Br em que o nó raiz de uma é filho do nó raiz da outra. Na Figura 2.1, à esquerda,
ilustra-se esta construção. Por construção, uma árvore binomial Br tem 2r nós, altura r
e a sua raiz tem grau r. Estes factos podem ser facilmente provados por indução em r.
2.2 Amontoados Relaxados
9
No contexto deste documento as árvores binomiais são ordenadas: os filhos de cada nó são
ordenados por ordem crescente do grau. Uma árvore binomial Br é também designada por
árvore binomial de grau r. A designação destas árvores advém do facto de existirem rl
nós com nı́vel l.
2.2 Amontoados Relaxados
Um amontoado é uma estrutura de dados baseada em árvores com raiz que satisfaz a
seguinte propriedade: a chave de um nó (mais precisamente, a chave do elemento associado
a um nó) é maior ou igual à chave do seu nó pai. Esta propriedade pressupõe uma ordem
total para as chaves e, quando é satisfeita, diz-se que a árvore é ordenada em amontoado.
Esta estrutura de dados ganha mais relevância com o facto de permitir implementações
eficientes de filas com prioridade.
Nesta secção discute-se em detalhe as duas versões de amontoados relaxados propostos
por Driscoll et al. [14], rank relaxed heaps e run relaxed heaps, ambas com base nos amontoados binomiais. Os rank relaxed heaps suportam as operações com a mesma complexidade
assimptótica amortizada que os amontoados de Fibonacci, enquanto que os run relaxed heaps suportam as operações remove, removeMin e meld em tempo O(log n) no pior caso
e todas as outras operações em tempo O(1) no pior caso. Para além dos amontoados relaxados serem a primeira concretização de amontoados a garantir estes limites assimptóticos no
pior caso, constituem também a base para o desenvolvimento de estruturas mais eficientes
como os two-tier relaxed heaps propostos recentemente por Elmasry et al. [16], compostos
por dois run relaxed heaps.
Os amontoados relaxados são constituı́dos por uma colecção de árvores binomiais ordenadas em amontoado. Porém, para garantir o tempo O(1) para algumas operações como o
decreaseKey, os amontoados relaxados permitem a existência de nós que não satisfazem
a propriedade de ordenação de amontoado, designados por nós maus. É importante notar
que o número de nós maus não pode ser arbitrário tendo em conta que se pretende que
a operação removeMin ocorra em tempo O(log n). Portanto, uma vez que esta operação
implica determinar o nó com menor chave e um nó mau pode ter a menor a chave, o número
de nós maus não poderá exceder O(log(n)).
Quer os rank relaxed heaps quer os run relaxed heaps não admitem mais do que log(n)
nós activos, nos quais se incluem os possı́veis nós maus. Para garantir esta propriedade é
necessário um conjunto de transformações para gerir eficientemente a estrutura de dados.
2.2 Amontoados Relaxados
0
1
7
2
10
10
7
5
12
10
9
0
13
12
11
14
Figura 2.2. Exemplo de um amontoado relaxado com chaves inteiras. Este amontoado tem 4 árvores binomiais e
2 nós activos, os nós com chave 5 e 0. Note-se que as árvores binomiais são ordenadas por grau, i.e., os filhos de
cada nó estão ordenados por grau, e estão ordenadas em amontoado à excepção dos nós activos.
Embora os rank relaxed heaps sejam menos flexı́veis quanto à ocorrência de nós maus, as
transformações são idênticas. Deste modo começar-se-á por explicar as transformações e a
concretização das operações para os rank relaxed heaps. De seguida discute-se a adaptação
das transformações para os run relaxed heaps. No final discutem-se alguns detalhes importantes para a implementação eficiente dos amontoados relaxados.
2.2.1 Rank Relaxed Heaps
Um rank relaxed heap é constituı́do por um conjunto de árvores binomiais, onde existem
nós que são distinguidos por activos, e que satisfazem as seguintes propriedades:
1. existe no máximo uma árvore binomial no amontoado cuja raiz tenha um dado grau;
2. cada árvore binomial é ordenada em amontoado, embora possa existir no máximo um
nó activo com grau r para cada grau r em toda a colecção;
3. cada nó activo no amontoado tem de ser o filho de maior grau de algum nó;
4. cada nó de uma árvore binomial no amontoado tem os filhos ordenados por grau.
Na Figura 2.2.1 mostra-se um exemplo de um rank relaxed heap em que os nós com chave 5
e 0 são activos e, neste caso, maus. Note-se que estes nós violam a propriedade de ordenação
em amontoado uma vez que são menores que os seus pais.
Como referido acima, os amontoados relaxados são baseados em amontoados binomiais
e, de facto, têm a mesma estrutura que os amontoados binomiais: um conjunto de árvores
binomiais tal que cada árvore é ordenada em amontoado e existe no máximo uma árvore
binomial de cada grau. A principal diferença reside na existência de nós maus, i.e., nós que
não respeitam a propriedade de ordem do amontoado.
Da primeira propriedade de rank relaxed heap tem-se que existe no máximo uma árvore
binomial de grau r na colecção para cada grau r e, dado o número n de elementos no
2.2 Amontoados Relaxados
11
amontoado, podemos determinar quais as árvores na colecção pela análise da representação
binária de n. Uma árvore binomial de grau r, Br , tem 2r nós. Portanto, considerando a
representação binária de n, o número de árvores binomiais será igual ao número de bits
P
a 1. Note-se que a representação binária de n tem blog(n)c + 1 bits e n = blog(n)c
bi 2i ,
i=0
onde bi é o i-ésimo bit na representação binária de n. Logo, a árvore binomial Bi surge no
amontoado se e só se bi = 1. Por exemplo, se considerarmos um amontoado com 6 nós, em
binário 110, existem duas árvores binomiais B1 e B2 com 2 e 4 nós respectivamente. Esta
análise implica ainda que num amontoado com n elementos existem no máximo blog(n)c+1
árvores binomiais.
A segunda propriedade permite inferir que existem no máximo blog(n)c nós activos. Da
análise acima da representação binária do número n tem-se que Bblog(n)c é a maior árvore
possı́vel no amontoado. Uma vez que todos os nós têm grau inferior ao seu pai e que o nó
raiz da árvore Bblog(n)c tem o maior grau, blog(n)c, tem-se que todos os nós têm no máximo
grau blog(n)c. Por outro lado, pela segunda propriedade, tem-se que existe no máximo um
nó activo por cada grau. Logo, existem no máximo blog(n)c nós activos.
As terceira e quarta propriedades são determinantes para a implementação das operações
sobre o amontoado com os tempos de execução mencionados acima. Em particular permitem localizar os nós activos e realizar várias transformações no amontoado de forma eficiente. Estas propriedades serão analisadas em maior detalhe na concretização das operações.
Antes de definir as operações, é necessário introduzir alguns detalhes a respeito da
representação dos rank relaxed heaps. Com vista à simplificação da descrição das operações,
assuma-se que existe um nó auxiliar head cuja chave terá sempre o menor valor possı́vel,
i.e., key[head ] < key[a] qualquer que seja o nó a, e que tem como filhos todos os nós raiz
das árvores binomiais no amontoado, ordenados por grau. Desta forma nenhum destes nós
poderá vir a ser activo, todos os nós no amontoado têm nó pai e, importante em algumas
situações que se seguem, todos os nós activos têm nó avô definido. Em relação aos nós,
cada nó a tem os seguintes atributos:
1.
2.
3.
4.
key[a], a chave do elemento associado ao nó a;
parent[a], o nó pai do nó a;
rank [a], o grau do nó a;
child [a][r], o filho do nó a com grau r, em que 0 ≤ r < rank [a].
É ainda necessário guardar o nó activo active[r] para cada grau r, caso exista, e uma
referência min para o nó com a chave mı́nima. Nota-se que estas são definições abstractas
dos atributos e que não pressupõem a utilização de uma estrutura de dados particular. No
2.2 Amontoados Relaxados
12
entanto é indispensável que os atributos sejam acessı́veis em tempo O(1) e a implementação
terá de garantir isso. Na Secção 2.3 discutir-se-ão os detalhes a ter em conta para uma
implementação eficiente das estruturas de dados. Um rank relaxed heap é inicializado da
seguinte forma:
makeRankRelaxedHeap(n)
1
2
3
4
5
6
7
8
n é a capacidade deste amontoado
min ← nil
key[head ] ← −∞
parent[head ] ← nil
rank [head ] ← 0
for r ← 0 to blog(n)c
do child [head ][r] ← nil
active[r] ← nil
Operação decreaseKey
Os rank relaxed heaps permitem executar a operação decreaseKey em tempo O(1) amortizado. Esta operação será a mais difı́cil de concretizar uma vez que, ao diminuir-se a chave
de um elemento do amontoado, pode criar-se um novo nó mau e portanto activo. Este facto
implica que uma única operação de diminuição de chave pode fazer com que as propriedades 2 e 3 se deixem de verificar. A dificuldade é então restaurar estas duas propriedades
garantindo um tempo de execução O(1) amortizado.
Considere-se um nó a ao qual se diminui a chave key[a]. É importante salientar que caso
a seja raiz de uma árvore binomial do amontoado, a nunca se tornará num nó mau, note-se
que key[head ] = −∞, e portanto nunca se tornará activo. Seja r o grau e p o nó pai do nó
a, i.e., rank [a] = r e parent[a] = p. A diminuição do valor da chave key[a] conduz a quatro
casos possı́veis:
1.
2.
3.
4.
key[a] ≥ key[p];
key[a] < key[p], a é o último filho e não existe outro nó activo com grau r;
key[a] < key[p], a é o último filho e existe outro nó activo com grau r;
key[a] < key[p] e a não é o último filho.
Os dois primeiros casos resolvem-se sem dificuldade. No primeiro caso o nó a é bom, logo se
for activo pode passar a inactivo. Neste caso o nó a não poderia ser mau antes da operação,
caso contrário continuaria a ser mau uma vez que a chave diminui. Contudo poderia ainda
2.2 Amontoados Relaxados
13
assim estar marcado como activo devido a operações anteriores, e.g., a chave key[p] pode
ter diminuı́do de valor numa operação anterior. No segundo caso o nó a é mau e portanto
terá de ser marcado como activo, o que pode ser feito uma vez que é último filho e não
existe outro nó activo com grau r. Portanto, em ambos os casos todas as propriedades
de rank relaxed heap são verificadas. O terceiro e quarto casos levantam mais dificuldades,
uma vez que é necessário realizar transformações nas árvores para garantir as propriedades.
No terceiro caso o nó a não pode ser marcado activo uma vez que existe outro nó activo
com grau r e, portanto, a propriedade 2 não se verificaria. No caso quatro o nó a não pode
ser marcado activo porque não é o último filho de p, caso contrário a propriedade 3 não se
verificaria. Deste modo, uma vez que nos terceiro e quarto casos o nó a é mau e não pode
ser marcado activo, é necessário introduzir um conjunto de transformações para reduzir o
número de nós activos e garantir que todos os nós activos são últimos filhos.
Dado um nó a e um novo valor v para a chave key[a], a operação decreaseKey definese da seguinte forma:
decreaseKey(a, v)
1 if key[a] < v
2
then error “a nova chave é maior do que a chave actual”
3
else key[a] ← v
4
update(a)
A última instrução, update(a), verifica se a deve ficar activo e realiza as transformações
necessárias no amontoado, de forma a restaurar as propriedades de rank relaxed heap. Se
key[a] ≥ key[p] e a estiver marcado como activo, i.e., active[r] = a, então a deverá ser
marcado inactivo, i.e., active[r] = nil. Se key[a] < key[p], a for o último filho de p e não
existir nenhum nó activo com grau r, i.e., active[r] = nil, então a deverá ser marcado
como activo, i.e., active[r] = a. Se key[a] < key[p] e já se verificar active[r] = a, então não
é necessário fazer nada. Nos outros casos em que key[a] < key[p] é necessário realizar uma
ou mais das seguintes transformações:
1. pairTransform, aplica-se quando a é o filho de maior grau, i.e., o último filho, e
existe um nó activo com grau r diferente de a;
2. goodSiblingTransform, aplica-se quando a não é último filho e o irmão direito s,
i.e., s = child [p][r + 1], não é activo, i.e., active[r + 1] 6= s;
3. activeSiblingTransform, aplica-se quando a não é último filho e o irmão direito é
activo, i.e., active[r + 1] = s.
2.2 Amontoados Relaxados
14
Note-se que a só será marcado activo após a execução das transformações, quando não
existir outro nó activo com grau r. O procedimento update define-se da seguinte forma:
update(a)
1 r ← rank [a]
2 p ← parent[a]
3 if key[a] ≥ key[p]
4
then if active[r] = a
5
then active[r] ← nil
6
else key[a] < key[p]
7
if r = rank [p] − 1 a é o último filho de p
8
then if active[r] = nil
9
then active[r] = a
10
else if active[r] 6= a
11
then pairTransform(a)
12
else a não é o último filho de p
13
s ← child [p][r + 1] s é o irmão direito de a
14
if active[r + 1] = s se s é activo
15
then activeSiblingTransform(a)
16
else goodSiblingTransform(a)
No caso da transformação pairTransform tem-se que a é um nó mau e que existe um
nó activo b com grau r, em que ambos são últimos filhos. O objectivo desta transformação
é reduzir o número de nós activos em pelo menos um nó por forma a resolver o conflito
entre o nó a e o nó activo com grau r. Na Figura 2.3 ilustra-se a execução da transformação
pairTransform. Sejam pa o nó pai de a, pb o nó pai de b, ga o nó avô de a, i.e., nó
pai de pa, e gb o nó pai de b, i.e., nó pai de pb. Em primeiro lugar os nós a e b são
removidos do amontoado, constituindo duas árvores binomiais de grau r com raı́zes a e b, e
são combinadas para formar uma árvore binomial de grau r +1. Sem perda de generalidade
assuma-se que key[a] > key[b]. A árvore resultante terá grau r + 1, raiz b e o último filho
b será o nó a. Em segundo lugar, uma vez que os nós pa e pb tinham grau r + 1 antes de
perderem o último filho (agora têm grau r), a árvore com raiz b irá substituir um deles.
Assuma-se sem perda de generalidade que key[pa] < key[pb]. Então, caso pb seja um nó
activo, pb é marcado inactivo e, enquanto filho do nó gb, é substituı́do pelo nó b. Finalmente
o nó pb é colocado como o filho de grau r do nó pa. Importa referir que estas operações
2.2 Amontoados Relaxados
15
ga
4
1
a)
pa
5
7
gb
30
12
10
5
8
3
1
pb
a
14
20
15
11
22
25
15
11
13
2
b
22
27
24
21
10
36
ga
4
1
b)
pa
5
7
gb
12
30
10
5
8
3
1
pb
14
20
13
b
15
22
25
15
11
10
2
a
21
27
22
36
11
24
Figura 2.3. Aplicação da transformação pairTransform ao nó a cuja chave foi diminuı́da para 11. O nó b é um
nó activo com o mesmo grau que o nó a. A numeração dos cortes e uniões ilustra uma ordem possı́vel das operações.
não afectam os restantes nós do amontoado e que ou a deixa de ser mau ou b deixa de ser
activo. Portanto, tendo em conta que a deveria de ser marcado activo, o número de nós
activos foi reduzido em pelo menos um. Este facto deve-se a que ao combinar os nós a e
b garante-se que um deles não é mau. A transformação pairTransform executa ainda
update(b) uma vez que b pode ser um nó mau em relação a gb. Em particular, dado
que pb não era necessariamente o último filho do nó gb, b pode não ser o último filho e,
por outro lado, pode existir outro nó activo com grau r + 1. Logo, podem ser necessárias
outras transformações. A Figura 2.4 ilustra o caso geral da transformação pairTransform
e a Figura 2.5 exemplifica o caso em que o resultado de combinar os nós a e b produz um
nó activo. Adiante ver-se-á como resolver este caso. A transformação pairTransform
define-se da seguinte forma:
2.2 Amontoados Relaxados
16
pairTransform(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
r ← rank [a]
b ← active[r]
active[r] ← nil
pa ← parent[a]
pb ← parent[b]
ga ← parent[pa]
gb ← parent[pb]
c ← combine(a, b)
if key[pa] ≤ key[pb]
then child [pa][r] ← pb tornar pb o último filho de pa
parent[pb] ← pa
child [gb][r + 1] ← c substituir pb enquanto filho de gb por c
parent[c] ← gb
rank [pb] ← rank [pb] − 1
if active[r + 1] = pb
then if key[c] < key[gb]
then active[r + 1] = c
else active[r + 1] = nil
else update(c)
else child [pb][r] ← pa tornar pa o último filho de pb
parent[pa] ← pb
child [ga][r + 1] ← c substituir pa enquanto filho de ga por c
parent[c] ← ga
rank [pa] ← rank [pa] − 1
if active[r + 1] = pa
then if key[c] < key[ga]
then active[r + 1] = c
else active[r + 1] = nil
else update(c)
Na definição da transformação pairTransform, linha 8, é invocada a operação combine. Dados dois nós a e b com o mesmo grau r, esta operação retorna uma árvore com
grau r + 1 que resulta de combinar a sub-árvore com raiz a e a sub-árvore com raiz b.
2.2 Amontoados Relaxados
ga
gb
ga
17
gb
k(pa)<k(pb)
Br
pa
Br
a
Br
pb
Br
Br
pa
Br
b
Br
pb
Br
Br
c
Br
Br
d
Br
Figura 2.4. Caso geral da transformação pairTransform. Os nós c e d são a ou b mediante a comparação da
chaves key[a] e key[b].
ga
pa
gb
4
1
c)
a
1
5
3
2
30
12
10
5
pb
8
2
14
20
15
13
b
22
0
15
27
21
11
13
22
36
14
24
ga
pa
gb
4
d)
1
1
5
3
5
12
30
10
0
pb
22
b=c
8
2
20
13
21
15
22
a
2
14
15
11
13
22
36
14
24
Figura 2.5. Aplicação da transformação pairTransform ao amontoado b) da Figura 2.3 após uma operação
decreaseKey. Primeiro a chave do nó b passou de 25 para 0, constituindo um nó activo, e numa segunda operação
a chave do nó a passou de 7 para 2. Uma vez que a e b têm o mesmo grau, é necessário aplicar a transformação
pairTransform ao nó a conduzindo ao amontoado d). Neste caso ga = head e o nó c, que resulta de combinar a
e b, fica activo e requer outra transformação. Note-se que c não é o último filho.
Se key[a] ≤ key[b], então a árvore retornada terá como raiz o nó a e o nó b passa a ser
o último filho de a. Se key[a] > key[b] verifica-se o oposto. Porém esta operação pode
fazer com que a propriedade 3 não se verifique. Assuma-se, sem perda de generalidade,
que key[a] ≤ key[b]. Se antes da operação combine o último filho do nó a for activo, i.e.,
active[r − 1] = child [a][r − 1], após a operação esse nó continuará activo mas já não será o
último filho uma vez que o grau do nó a passou a ser r + 1 e o último filho é o nó b. Nestas
2.2 Amontoados Relaxados
c
Br
18
c
xc
d
Br
Br
Br
xd
xd
d
Br
Br
Br
xa
Br
Figura 2.6. Aplicação da operação clean ao nó xc.
situações é necessário aplicar a operação clean que permuta o filho activo de a com grau
r − 1 com o filho r − 1 de b. Note-se que se o filho de a com grau r − 1 for activo, o filho
de b com grau r − 1 não pode ser activo pela propriedade 2. Portanto a operação clean
produz sempre o efeito desejado, restaurando a propriedade 3. A Figura 2.6 ilustra esta
operação no caso geral. A operação combine define-se da seguinte forma:
combine(a, b)
1
2
3
4
5
6
7
8
9
10
11
12
a e b são dois nós com o mesmo grau r
if key[a] ≤ key[b]
then child [a][r] ← b
parent[b] ← a
rank [a] ← rank [a] + 1
c←a
else child [b][r] ← a
parent[a] ← b
rank [b] ← rank [b] + 1
c←b
clean(child [c][r − 1])
return c
Considere-se agora a transformação activeSiblingTransform invocada na operação
update, linha 15. Esta transformação aplica-se quando o nó a é mau, não é o último filho
e o seu irmão direito é activo. Recorde-se que p = parent[a] é o pai de a, r = rank [a] é
o grau de a e s = child [p][r + 1] é o irmão direito de a. Pela propriedade 3 tem-se que
s é o último filho de p e, portanto, p tem grau r + 2 uma vez que a tem grau r e s tem
grau r + 1. Seja g = parent[p] o nó pai de p, avô de a. A Figura 2.7 ilustra a sequência
de operações da transformação activeSiblingTransform. Começa-se por remover o nó
mau a e nó activo s do amontoado. De seguida remove-se o nó p do amontoado que agora
2.2 Amontoados Relaxados
19
g
k(a) > k(s)
s
a
B r+1
g
Br
p
p
Br
Br
a
Br
s
B r+1
g
k(a) < k(s)
a
Br
p
Br
s
B r+1
Figura 2.7. Caso geral da transformação activeSiblingTransform.
tem grau r uma vez que perdeu os dois filhos de maior grau. Em terceiro lugar aplicam-se
duas vezes a operação combine. Primeiro aos nós p e a com grau r dando origem a uma
árvore de grau r + 1 com raiz a. Neste caso a raiz é a porque a era um nó mau, i.e.,
key[a] < key[p]. A árvore de grau r + 1 é combinada de seguida com a sub-árvore com raiz
s dando origem a uma árvore com grau r + 2. Finalmente a raiz c da nova árvore de grau
r + 2 passa a ser o filho de grau r + 2 de g. Tal como na transformação pairTransform
é necessário verificar se o nó c é mau, i.e., se key[c] < key[g]. E da mesma forma que na
transformação pairTransform, basta invocar update(c) no final. É importante notar
que esta transformação também reduz o número de nós activos em pelo menos um. No
inı́cio existiam dois nós activos, o nó mau a e o nó activo s, e no final apenas c poderá vir
a ser activo. Todos os outros nós do amontoado permanecem inalterados. A transformação
activeSiblingTransform define-se da seguinte forma:
2.2 Amontoados Relaxados
20
activeSiblingTransform(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
r ← rank [a]
p ← parent[a]
g ← parent[p]
s ← child [p][r + 1]
active[r + 1] ← nil s era activo, i.e., active[r + 1] = s
rank [p] ← rank [p] − 2 p perde os dois filhos de maior grau
a ← combine(a, p) como a era mau, i.e., key[a] < key[p], a raiz continua a ser a
c ← combine(a, s) c é raiz de uma árvore de grau r + 2
child [g][r + 2] ← c
parent[c] ← g
if active[r + 2] = p depois de combinar p com a, p já não pode ser activo
then active[r + 2] = nil
update(c)
A operação update depende ainda da transformação goodSiblingTransform. Esta
transformação aplica-se quando o nó a é mau, não é o último filho e o irmão direito não
é activo. Como nos casos anteriores, p = parent[a] é o pai de a, r = rank [a] é o grau
de a, s = child [p][r + 1] é o irmão direito de a e g = parent[p] o pai de p. Ao contrário
do que acontece na transformação activeSiblingTransform, aqui s pode não ser o
último filho. A transformação começa por distinguir dois casos. A Figura 2.8 ilustra a
transformação goodSiblingTransform no caso geral. Se o último filho c de s não for
activo, basta aplicar a operação clean ao nó a e este permuta com o nó c, passando a ser
um último filho de s. Caso exista outro nó activo com grau r, é ainda necessário aplicar
a transformação pairTransform ao nó a. Na prática aplica-se a operação update ao
nó a após a operação clean. Este é o caso do amontoado d) da Figura 2.5, em que é
necessário aplicar a transformação goodSiblingTransformation. No segundo caso o
nó c é activo e portanto basta aplicar a transformação pairTransform ao nó a, garantindo
que s continua a ser filho de p. Note-se que neste caso o pai de s e avô de c é o nó p, logo
à partida poderia haver problemas com a aplicação da operação pairTransform. Porém
s não é activo e portanto é um nó bom, i.e., key[p] < key[s], sendo que no resultado da
transformação pairTransform o nó s continua a ser filho do nó p. Apenas é necessário
garantir que s também continua a ser filho de p quando key[p] = key[s], o que se verifica na
definição da transformação pairTransform, linha 9. É importante referir que, embora
2.2 Amontoados Relaxados
g
g
p
p
21
a)
Br
a
s
Br
Br
...
Br
c
...
c
s
Br
Br
a
Br
Br
g
g
p
p
b)
Br
a
Br
s
Br
...
c
Br
Br
s
Br
COMBINE
a
c
Br
Br
...
Figura 2.8. Caso geral a), quando o nó c não é activo, e caso geral b), quando o nó c é activo, da transformação
goodSiblingTransform.
no segundo caso a transformação pairTransform garante que o número de nós activos
é reduzido em pelo menos um, no primeiro caso pode não ocorrer redução do número de
nós activos. No entanto, se a operação update não reduzir o número de nós activos no
primeiro caso, é porque não existe outro nó activo com grau r e as propriedades de rank
relaxed heap são válidas. A transformação goodSiblingTransform define-se da seguinte
forma:
goodSiblingTransform(a)
1
2
3
4
5
6
7
8
9
r ← rank [a]
p ← parent[a]
g ← parent[p]
s ← child [p][r + 1] irmão direito de a
c ← child [s][r] último filho de s
if active[r] = c se c for activo
then pairTransform(a)
else clean(a)
update(a)
Embora não seja óbvio, a operação decreaseKey decorre em tempo O(1) amortizado.
Cada uma das transformações descritas opera em tempo O(1) no pior caso, excluindo a
possı́vel execução no final de outra transformação. Pela propriedade 2 de rank relaxed heap
2.2 Amontoados Relaxados
22
existem no máximo blog(n)c nós activos. Portanto, tendo em conta que cada transformação
reduz o número de nós activos em pelo menos um e que pode executar outra transformação,
a operação decreaseKey decorrerá em tempo O(log n) no pior caso. Porém, considere-se
m operações decreaseKey. Cada uma destas operações pode introduzir no máximo um
nó activo ao diminuir a chave do mesmo. Por outro lado cada transformação reduz um nó
activo quando é executada. Logo, independentemente do número de transformações que
é executado em cada operação decreaseKey, em m operações decreaseKey apenas
podem ser executadas m transformações no máximo admitindo que no inı́cio não existiam
nós activos. Portanto, m operações decreaseKey decorrem em tempo O(m) no pior caso,
i.e., a operação decreaseKey decorre em tempo O(1) amortizado.
Operação removeMin
A operação removeMin encontra e retorna o nó com a menor chave no amontoado. O nó
com menor chave ou é uma raiz das árvores binomiais no amontoado, i.e., um dos filhos
do nó head , ou é um dos nós activos. Como discutido anteriormente, o número de árvores
binomiais no amontoado é no máximo blog(n)c+1 e o número de nós activos no amontoado é
no máximo blog(n)c. Logo o nó com menor chave pode ser encontrado em tempo O(log(n)),
bastando percorrer os filhos do nó head e os nós activos. Aqui pressupõe-se que é possı́vel
enumerar os nós activos de forma eficiente, ver-se-á adiante como fazer.
Após determinar o nó com a menor chave, denotado por nó min, este será removido
do amontoado. A Figura 2.9 ilustra a eliminação do nó min no caso deste se encontrar
na raiz de uma árvore binomial no amontoado, i.e., quando parent[min] = head . Primeiro
retira-se o nó raiz y no amontoado com menor grau e adicionam-se todos os seus filhos
como filhos do nó head , i.e., os filhos de y passam a ser raı́zes do amontoado. Note-se
que esta operação não produz árvores binomiais com o mesmo grau no amontoado, basta
observar que todos os nós filhos de y têm grau distinto e inferior ao grau de y e y é a
raiz com menor grau. Logo, as propriedades de rank relaxed heap permanecem válidas.
Caso o nó min seja o próprio y, a operação removeMin está concluı́da. Caso min 6= y é
necessário recombinar o nó y com os filhos do nó min e substituir o nó min no amontoado
pela árvore resultante da recombinação. Na recolocação dos filhos de y e na operação de
recombinação de y com os filhos do nó min dever-se-á desmarcar os nós que estejam activos
e que deixam de o ser. É ainda necessário verificar se a substituição do nó min dá origem
a um novo nó activo. Uma vez que o número de filhos de um nó é no máximo blog(n)c e
que a operação combine decorre em tempo O(1) no pior caso, tem-se que estas operações
2.2 Amontoados Relaxados
...
y
x0 . . .
Br
...
min
y0 . . . yr
23
xk
Bk
y0
...
yr
...
COMBINE
y
x0
...
xk
Figura 2.9. Operação removeMin quando o nó min é a raiz de uma das árvores binomiais no amontoado. Quando
o nó min é um dos nós activos a operação é idêntica.
decorrem em tempo O(log n) no pior caso. Repare-se que a operação removeMin não
aumenta o número de nós activos e, portanto, não afecta o tempo amortizado da operação
decreaseKey. A operação removeMin define-se da seguinte forma:
2.2 Amontoados Relaxados
removeMin()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
if rank [head ] = 0 se o amontoado for vazio
then return nil
min ← head
y ← nil
for r = 0 to blog(n)c procurar o nó min e o filho y do nó head com menor grau
do x ← child [head ][r] filho de grau r do nó head
if x 6= nil ∧ key[min] > key[x]
then min ← x
if y = nil verificar se y já foi encontrado
then y ← x
x ← active[r] nó activo de grau r
if x 6= nil ∧ key[min] > key[x]
then min ← x
for r = 0 to rank [y] adicionar todos os filhos de y ao nó head
do child [head ][r] ← child [y][r]
parent[child [y][r]] ← head
if active[rank [y] − 1] = child [y][rank [y] − 1] se o último filho de y for activo
then active[rank [y] − 1] = nil
rank [y] ← 0
p ← parent[min]
if active[rank [min]] = min se min for um nó activo
then active[rank ] ← nil
if min 6= y
then for r = 0 to rank [min] recombinar y com todos os filhos do nó min
do y ← combine(y, child [min][r])
child [p][rank [min]] ← y
parent[y] ← p
if key[y] < key[p]
then active[rank [y]] = y isto só ocorre se o nó min era activo
else active[rank [y]] = nil
return min
24
2.2 Amontoados Relaxados
25
Outras Operações
Para além das operações já descritas, os rank relaxed heaps também suportam as operações
minimum e insert com tempo O(1) no pior caso e as operações remove e meld em tempo
O(log(n)) no pior caso. Nesta Secção ver-se-á como concretizar as operações minimum,
insert e meld. A operação remove é em tudo idêntica à operação removeMin, apenas
o nó é dado como argumento em vez de ser o nó min.
A operação minimum pode ser facilmente definida com tempo O(1) no pior caso alterando a definição da operação decreaseKey por forma a manter o nó min actualizado.
Nesse caso a operação deleteMin não precisa de procurar o nó com a menor chave no
inı́cio, mas terá de actualizar o nó com a menor chave depois de eliminar o nó min. Reparese que estas alterações não alteram os tempos das operações decreaseKey e deleteMin.
No primeiro caso basta comparar o nó a actualizar com o nó min actual e no segundo caso
basta fazer a procura no final em vez de no inı́cio. Da mesma forma a operação insert
terá de actualizar o nó min aquando da inserção de um novo nó. Com estas alterações o
nó min será sempre o nó com a menor chave e a operação minimum só tem de retornar
esse nó, o que é feito em tempo O(1) no pior caso.
Definir a operação insert com tempo O(log(n)) no pior caso é relativamente simples.
Cria-se um novo nó x e, enquanto existir uma raiz y no amontoado, i.e., y é filho do nó
head , com o mesmo grau que x, substitui-se y pelo resultado de combine(x, y). Uma vez
que o número de filhos do nó head é no máximo blog(n)c + 1 e que a operação combine
decorre em tempo O(1) no pior caso, tem-se que esta versão da operação insert decorre
em tempo O(log(n)) no pior caso. Veja-se agora como concretizar a operação insert com
tempo O(1) no pior caso. A ideia é também recombinar as raı́zes, contudo será feito de
forma gradual. O nó head passa a poder ter filhos com o mesmo grau, de facto poderá
ter no máximo dois com o mesmo grau r para cada r. Cada par de raı́zes com o mesmo
grau é mantido numa lista de pares e, sempre que for inserido um novo nó, a operação
insert retira um par de raı́zes da lista de pares e aplica a operação combine reduzindo
o número de pares, i.e., o número de raı́zes com o mesmo grau, em uma unidade. Note-se
que desta operação pode surgir um novo par, i.e., pode já existir outra raiz com o mesmo
grau. Portanto, o número de pares de raı́zes com o mesmo grau pode manter-se. Todavia,
dado que o número de raı́zes é finito, sucessivas inserções levarão à diminuição do número
de pares que será sempre inferior a blog(n)c + 1. Uma vez que a operação combine decorre
em tempo O(1) no pior caso, a operação insert também decorre em tempo O(1) no pior
caso. Existe apenas mais um detalhe a ter em conta, a procura do nó com menor chave
2.2 Amontoados Relaxados
26
terá de ser modificada. A forma mais simples é, na operação removeMin onde se procura
entre as raı́zes e os nós activos o nó com menor chave, resolver todos os conflitos na lista de
pares. Repare-se que isto não altera o tempo de execução da operação removeMin pois,
embora o número de raı́zes possa ser agora 2 blog(n)c + 2, este continua a ser O(log(n)).
A operação meld, i.e., a fusão de dois amontoados, pode ser definida com tempo
O(log(n)) de forma idêntica à primeira versão da operação insert discutida antes. Portanto, o processo consiste em juntar todas as raı́zes por ordem crescente de grau e aplicar
a operação combine tantas vezes quanto as necessárias. Assumindo-se que os amontoados
têm n e n0 elementos, a operação combine tem ser aplicada blog(n)c + blog(n0 )c + 1 vezes
no pior caso. Logo, a operação meld decorre em tempo O(log(n)) no pior caso.
2.2.2 Run Relaxed Heaps
Tal como nos rank relaxed heaps, a ideia é permitir a ocorrência de nós maus no amontoado. Contudo, ainda que continuem a existir no máximo blog(n)c nós activos, existe maior
flexibilidade quanto à sua ocorrência. De facto no caso dos run relaxed heaps os nós activos podem ocorrer livremente no amontoado e não apenas em determinados locais. Esta
diferença permitirá definir a operação decreaseKey com tempo O(1) no pior caso.
Portanto, um run relaxed heap é constituı́do por um conjunto de árvores binomiais, onde
existem nós que são distinguidos por activos, e que satisfazem as seguintes propriedades:
1. existe no máximo uma árvore binomial no amontoado cuja raiz tenha um dado grau;
2. cada árvore binomial é ordenada em amontoado, embora possam existir no máximo
blog(n)c nós activos em toda a colecção;
3. cada nó de uma árvore binomial no amontoado tem os filhos ordenados por grau.
Uma vez que os nós activos podem ocorrer livremente no amontoado, podem existir
sequências de dois ou mais irmãos activos. Estas sequências são designadas na literatura
por runs, daı́ a designação run relaxed heap. Quando um nó activo não faz parte de uma
sequência de nós activos, diz-se que é um nó singular. A principal dificuldade nestes amontoados é gerir os nós activos de forma a garantir os tempos desejados para as operações.
Para tal, considere-se a estrutura de dados auxiliar run-singleton:
1. para cada grau r existe uma lista singleList[r] que contém todos os nós activos singulares
com grau r;
2. a lista runList guarda o último nó, i.e., o nó de maior grau, de cada sequência de nós
activos;
2.2 Amontoados Relaxados
27
3. a lista pairList guarda os graus r para os quais a lista singleList[r] tem mais de dois
elementos, i.e., |singleList[r]| ≥ 2.
Dado que existem no máximo blog(n)c nós activos, tem-se que esta estrutura requer no
máximo O(log(n)) espaço. Contudo, isto implica que uma implementação eficiente utilize,
por exemplo, listas duplamente ligadas. Logo, para garantir todas as operações com tempo
O(1) é necessário guardar informação a respeito da posição na lista em que cada nó ocorre.
Na prática cada nó deverá manter uma referência para a posição na lista, caso ocorra
em alguma das listas singleList[r] ou pairList. Note-se que um nó não pode ocorrer em
simultâneo em ambas as listas. Da mesma forma convém guardar para cada grau r, caso
existam mais de dois nós activos com grau r, a referência da sua posição na lista pairList.
Estas referências para os nós das listas são importantes para que se possam eliminar elementos em tempo O(1). Tendo em conta estas observações é então possı́vel concretizar as
seguintes operações em tempo constante:
1. addSingleton(x), adiciona o nó x com grau r à lista singleList[r] e, caso se verifique
|singleList[r]| ≥ 2, adiciona r à lista pairList;
2. removeSingleton(x), remove o nó x com grau r da lista singleList[r] e, caso se
verifique |singleList[r]| < 2, remove r da lista pairList;
3. addRun(x), adiciona o nó x à lista runList;
4. removeRun(x), remove o nó x da lista runList.
Na representação dos run relaxed heaps, cada nó terá os atributos vistos no caso dos rank
relaxed heaps e um quinto atributo booleano isActive. Este atributo permite marcar cada nó
como activo ou inactivo e determinar se um dado nó é activo em tempo constante. Repara-se
que a estrutura run-singleton não guarda todos os nós activos, apenas os singulares e último
nó de cada sequência de nós activos, pelo que não permite decidir em tempo constante se
um dado nó é activo ou não. A inicialização de um run relaxed heap é em tudo igual à
inicialização de um rank relaxed heap, acrescendo apenas a instrução isActive[x] ← false.
Antes de se discutirem as operações sobre o amontoado é útil definir as operações auxiliares setActive e setInactive. Dado um nó a, estas operações actualizam o estado de
a e a estrutura de dados run-singleton. Sejam r = rank [a] o grau de a, p = parent[a] o nó
pai de a, s = child [p][r + 1] o irmão direito de a e t = child [p][r − 1] o irmão esquerdo de a.
Note-se que s e t podem não existir, e.g., o nó a pode ser o último filho de p e nesse caso
não existe o nó s. A operação setActive começa por marcar o nó a activo e actualiza a
estrutura de dados run-singleton da seguinte forma:
2.2 Amontoados Relaxados
28
1. se os nós t e s não forem activos, então a é nó activo singular e basta ser adicionado
como nó singular, addSingleton(a);
2. se t não for activo e s for activo, então a passa a fazer parte de uma sequência
de nós activos e, se s for nó activo singular, é necessário efectuar as operações
removeSingleton(s) e addRun(s);
3. se t for activo e s não for activo, então a é o nó de maior grau numa sequência de nós
activos, i.e., o último nó da sequência, e é necessário efectuar a operação addRun(a)
e ou a operação removeSingleton(t) ou a operação removeRun(t) conforme t seja
um nó activo singular ou não, respectivamente (uma vez que t é activo, ou era singular
ou era o último nó de uma sequência);
4. se os nós t e s forem activos, então a faz parte de uma sequência de nós activos e
processam-se os nós s e t como nos casos 2 e 3, respectivamente.
Sejam s0 = child [p][r + 2] o irmão direito de s e t0 = child [p][r − 2] o irmão esquerdo de
t, que podem não existir. A operação dual, setInactive, começa por marcar o nó a não
activo e actualiza a estrutura de dados run-singleton da seguinte forma:
1. se os nós t e s não forem activos, então a era nó activo singular e basta efectuar a
operação removeSingleton(a);
2. se t não for activo e s for activo, então a fazia parte de uma sequência de nós activos e,
se s0 não existir ou não for activo, s era o último nó da sequência e é necessário efectuar
as operações removeRun(s) e addSingleton(s);
3. se t for activo e s não for activo, então a era o nó de maior grau numa sequência de nós
activos, i.e., o último nó da sequência, portanto efectua-se a operação removeRun(a),
e se t0 não existir ou não for activo, t passa a ser singular e efectua-se a operação
addSingleton(t), caso contrário t passa a ser o último da sequência e efectua-se a
operação addRun(t);
4. se os nós t e s forem activos, então a faz parte de uma sequência de nós activos e
processam-se os nós s e t como nos casos 2 e 3, respectivamente.
Tendo em conta que as operações addSingleton, removeSingleton, addRun e removeRun decorrem em tempo O(1) no pior caso, tem-se que as operações setActive e
setInactive também ocorrem em tempo O(1) no pior caso. Em detalhe, setActive e
setInactive definem-se da seguinte forma:
2.2 Amontoados Relaxados
setActive(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
r ← rank [a]
p ← parent[a]
if r < rank [p] − 1 se existir irmão direito de a
then s ← child [p][r + 1]
else s ← nil
if r > 0 se existir irmão esquerdo de a
then t ← child [p][r − 1]
else t ← nil
if r < rank [p] − 2 se existir irmão direito de s
then s0 ← child [p][r + 2]
else s0 ← nil
if r > 1 se existir irmão esquerdo de t
then t0 ← child [p][r − 2]
else t0 ← nil
isActive[a] ← true
if ¬ isActive[t] ∧ ¬ isActive[s]
then addSingleton(a)
else if ¬ isActive[t] ∧ isActive[s]
then if s0 = nil ∨ ¬ isActive[s0 ] se s for singular
then removeSingleton(s)
addRun(s)
else if isActive[t] ∧ ¬ isActive[s]
then if t0 = nil ∨ ¬ isActive[t0 ] se t for singular
then removeSingleton(t)
else removeRun(t)
addRun(a)
else if s0 = nil ∨ ¬ isActive[s0 ] se s for singular
then removeSingleton(s)
addRun(s)
0
if t = nil ∨ ¬ isActive[t0 ] se t for singular
then removeSingleton(t)
else removeRun(t)
29
2.2 Amontoados Relaxados
setInactive(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
r ← rank [a]
p ← parent[a]
if r < rank [p] − 1 se existir irmão direito de a
then s ← child [p][r + 1]
else s ← nil
if r > 0 se existir irmão esquerdo de a
then t ← child [p][r − 1]
else t ← nil
if r < rank [p] − 2 se existir irmão direito de s
then s0 ← child [p][r + 2]
else s0 ← nil
if r > 1 se existir irmão esquerdo de t
then t0 ← child [p][r − 2]
else t0 ← nil
isActive[a] ← false
if ¬ isActive[t] ∧ ¬ isActive[s]
then removeSingleton(a)
else if ¬ isActive[t] ∧ isActive[s]
then if s0 = nil ∨ ¬ isActive[s0 ] s torna-se singular
then removeRun(s)
addSingleton(s)
else if isActive[t] ∧ ¬ isActive[s]
then removeRun(a)
if t0 = nil ∨ ¬ isActive[t0 ] t torna-se singular
then addSingleton(t)
else addRun(t)
else if s0 = nil ∨ ¬ isActive[s0 ] s torna-se singular
then removeRun(s)
addSingleton(s)
0
if t = nil ∨ ¬ isActive[t0 ] t torna-se singular
then addSingleton(t)
else addRun(t)
30
2.2 Amontoados Relaxados
31
Operação decreaseKey
Os run relaxed heaps permitem executar a operação decreaseKey em tempo O(1) no pior
caso. A diferença em relação aos rank relaxed heaps reside nas transformações realizadas
para garantir as propriedades dos amontoados, nomeadamente na definição da operação
update. Nesta Secção discutir-se-ão as alterações e as novas transformações necessárias.
A operação update verifica se um dado nó deve ser activo ou não e, caso seja um nó
mau e não activo, marca-o como activo e actualiza a estrutura de dados run singleton. Uma
vez que esta operação aumenta o número de nós activos, a ideia consiste em tentar reduzir
um nó activo sempre que é adicionado um novo nó activo. Para isso verifica-se se existem
dois nós activos singulares com o mesmo grau e, caso existam, aplica-se a transformação
singletonTransform. Em segundo lugar verifica-se se existe alguma sequência de nós
activos e, caso exista, aplica-se a transformação runTransform. Quer a transformação
singletonTransform quer a transformação runTransform reduzem o número de
nós activos em pelo menos um. Note-se que, caso ambas as listas pairList e runList sejam
vazias, existe no máximo um nó activo por cada grau. Logo, existem no máximo blog(n)c
nós activos e, portanto, as condições de run relaxed heap verificam-se. A operação update
define-se da seguinte forma:
update(a)
1 p ← parent[a]
2 if key[a] ≥ key[p]
3
then if isActive[a]
4
then setInactive(a)
5
else if ¬ isActive[a] a não é activo e key[a] < key[p]
6
then setActive(a)
7
if pairList 6= ∅
8
then r ← removeFirst(pairList)
9
x ← removeFirst(singleList[r])
10
y ← removeFirst(singleList[r])
11
singletonTransform(x, y)
12
if runList 6= ∅
13
then x ← removeFirst(runList)
14
runTransform(x)
2.2 Amontoados Relaxados
32
As operações singletonTransform e runTrasnform consistem na combinação de
versões simplificadas das transformações discutidas para o caso dos rank relaxed heaps.
Os run relaxed heaps não exigem que apenas exista um grau activo por cada grau nem
que os nós activos tenham de ser os últimos filhos, portanto não será necessário realizar a
operação update no final das transformações pairTransform, activeSiblingTransform e goodSiblingTransform. Da mesma forma não é necessário realizar a operação
clean após ligar dois nós com o mesmo grau na operação combine. No que se segue
utiliza-se uma versão simplificada da operação combine, designada link, cuja única diferença é não invocar a operação clean. A operação pairTransform passa a receber dois
parâmetros e define-se da seguinte forma:
pairTransform(a, b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
setInactive(a)
setInactive(b)
r ← rank [a]
pa ← parent[a]
pb ← parent[b]
ga ← parent[pa]
gb ← parent[pb]
c ← link(a, b)
if key[pa] ≤ key[pb]
then child [pa][r] ← pb tornar pb o último filho de pa
parent[pb] ← pa
child [gb][r + 1] ← c substituir pb enquanto filho de gb por c
parent[c] ← gb
rank [pb] ← rank [pb] − 1
if isActive[pb]
then setInactive(pb)
if key[c] < key[gb]
then setActive(c)
else . . . da mesma forma, mas trocando a, pa e ga com b, pb e gb
A operação activeSiblingTransform passa a definir-se da seguinte forma:
2.2 Amontoados Relaxados
33
activeSiblingTransform(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
r ← rank [a]
p ← parent[a]
g ← parent[p]
s ← child [p][r + 1]
setInactive(a)
setInactive(s)
if isActive[p]
then setInactive(p)
rank [p] ← rank [p] − 2 p perde os dois filhos de maior grau
a ← link(a, p) como a era mau, i.e., key[a] < key[p], a raiz continua a ser a
c ← link(a, s) c é raiz de uma árvore de grau r + 2
child [g][r + 2] ← c
parent[c] ← g
if key[c] < key[g] se c for mau
then setActive(c)
E a operação goodSiblingTransform passa a retornar true se reduziu o número de
nós activos, false caso contrário, e define-se da seguinte forma:
goodSiblingTransform(a)
1
2
3
4
5
6
7
8
9
10
11
12
r ← rank [a]
p ← parent[a]
g ← parent[p]
s ← child [p][r + 1] irmão direito de a
c ← child [s][r] último filho de s
if isActive[c] se c for activo
then pairTransform(a, c)
return true pairTransform reduz pelo menos um nó activo
else setInactive(a)
clean(a)
setActive(a)
return false
Uma vez que a operação update deixou de ser invocada, todas as transformações decorrem
agora em tempo O(1) no pior caso.
2.2 Amontoados Relaxados
34
Dados dois nós activos a e b singulares com grau r, a transformação singletonTransform reduz o número de nós activos em pelo menos um, em tempo O(1) no pior caso.
Sejam pa = parent[a] o nó pai de a, sa = child [pa][r +1] o irmão direito de a, pb = parent[b]
o nó pai de b e sb = child [pb][r + 1] o irmão direito de b. Note-se que os nós sa e sb ou não
existem (quer a quer b podem ser últimos filhos) ou não são activos, caso contrário a e b
não seriam singulares. Existem quatro casos a considerar:
1. se a e b são ambos últimos filhos, i.e., rank [pa] = r + 1 and rank [pb] = r + 1, então
aplica-se a transformação pairTransform a a e b, cf. Figura 2.4;
2. se a é último filho e b não é último filho, então aplica-se a transformação goodSiblingTransform a b cf. Figura 2.8 e, caso não reduza o número de nós activos cf. Figura
2.8 a), aplica-se a transformação pairTransform aos nós a e b;
3. se a não é último filho e b é último filho, idêntico ao caso anterior trocando a com b;
4. se a e b não forem últimos filhos, então processam-se ambos os nós como nos casos 1 e 3
e, se a transformação goodSiblingTransform não reduzir o número de nós activos,
aplica-se no final a transformação pairTransform aos nós a e b.
Como a transformação pairTransform reduz sempre o número de nós activos em pelo
menos um, tem-se que a transformação singletonTransform também reduz o número
de nós activos.
A transformação runTransform aplica-se ao último nó a de uma sequência de nós
activos e reduz o número de nós activos em pelo menos um. Sejam p = parent[a] o nó
pai de a, t = child [p][r − 1] o irmão esquerdo de a e s = child [p][r + 1] o irmão direito
de a. Note-se que t existe sempre e é activo, uma vez que a é último de uma sequência
de nós activos. Por outro lado, s pode não existir se a for o último filho de p. Existem
dois casos a considerar. Se a for o último filho de p, então basta aplicar a transformação
activeSiblingTransform ao nó t cf. Figura 2.7. Se a não for último filho de p, então
aplica-se a transformação ilustrada na Figura 2.10. A transformação consiste em trocar os
nós t e a pelo penúltimo filho d e último filho c de s, respectivamente. É importante notar
que, se a tiver grau r, então t tem grau r − 1, s tem grau r + 1, d tem grau r − 1 e c tem
grau r. Portanto, a árvore binomial continua consistente. Também importante é o facto
dos nós c e d poderem ser activos e de poderem continuar a ser activos, sendo necessário
actualizar a estrutura de dados run-singleton face à troca. Em particular porque os nós c e
d podiam fazer parte de uma sequência de nós activos ou vir a integrar uma nova sequência
nós activos. Os nós t, a e s são combinados para formar uma árvore de grau r + 1 com raiz
2.2 Amontoados Relaxados
35
p
Br−1
t
a
s
Br−1
Br
Br−1
...
d
c
Br−1
Br
p
Br−1
...
d
c
Br−1
Br
LINK(t,a)
t
Br−1
s
a
Br−1
Br
Figura 2.10. Aplicação da transformação runTransform quando a não é o último filho de p. O nó que resulta
de ligar a e t é activo, uma vez que t e a eram activos. Se d e c forem activos, é necessário verificar se o continuam
a ser.
c que passará a ser o filho de grau r + 1 de p, i.e., substitui s. Note-se que da recombinação
dos nós t, a e c pode resultar um nó activo, a raiz da nova árvore pode ser um nó mau. No
entanto foi reduzido o número de nós activos em pelo menos um, visto os nós a e t serem
ambos activos. A transformação runTransform decorre também em tempo O(1) no pior
caso, note-se que todas as operações envolvidas decorrem em tempo constante.
As transformações singletonTransform e runTransform definem-se da seguinte
forma:
2.2 Amontoados Relaxados
singletonTransform(a, b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
r ← rank [a]
pa ← parent[a]
pb ← parent[b]
if r < rank [pa] − 1 se existir irmão direito de a
then sa ← child [pa][r + 1]
else sa ← nil
if r < rank [pb] − 1 se existir irmão direito de b
then sb ← child [pb][r + 1]
else sb ← nil
if sa = nil ∧ sb = nil se a e b forem últimos filhos
then pairTransform(a, b)
else if sa = nil ∧ sb 6= nil se a for último filho mas b não
then if ¬goodSiblingTransform(b)
then pairTransform(a, b)
else if sa 6= nil ∧ sb = nil se a não for último filho mas b for
then if ¬goodSiblingTransform(a)
then pairTransform(a, b)
else se a e b não forem últimos filhos
if ¬goodSiblingTransform(a)
then if ¬goodSiblingTransform(b)
then pairTransform(a, b)
36
2.2 Amontoados Relaxados
runTransform(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
r ← rank [a]
p ← parent[a]
t ← child [p][r − 1] t é o irmão esquerdo de a
if r < rank [p] − 1 se existir irmão direito de a
then s ← child [p][r + 1]
d ← child [s][r − 1] penúltimo filho de s
c ← child [s][r] último filho de s
if isActive[d]
then setInactive(d)
if isActive[c]
then setInactive(c)
else s ← nil
if s = nil se a for o último filho de p
then activeSiblingTransform(t)
else setInactive(a)
setInactive(t)
rank [s] ← rank [s] − 2 o nó s perde os dois últimos filhos
child [p][r − 1] ← d d substitui t
parent[d] ← p
child [p][r] ← c c substitui a
parent[c] ← p
t ← link(t, s)
e ← link(t, a)
child [p][r + 1] ← e e substitui s
parent[e] ← p
if key[c] < key[p]
then setActive(c)
if key[d] < key[p]
then setActive(d)
if key[e] < key[p]
then setActive(e)
37
2.3 Detalhes de Implementação
38
Outras operações
As restantes operações são em tudo idênticas às discutidas no caso dos rank relaxed heaps.
Apenas é necessário ter em conta que no caso das operações removeMin, remove, insert
e meld ter-se-á que utilizar a operação link em vez da operação combine para combinar
os nós. E que em todas as operações os nós passam a ser marcados activos ou inactivos
com as operações setActive e setInactive, respectivamente.
Os tempos das operações são também os mesmos, i.e., as operações removeMin, remove e meld decorrem em tempo O(log(N )) no pior caso e as operações insert e minimum decorrem em tempo O(1) no pior caso, tal como agora a operação decreaseKey.
2.3 Detalhes de Implementação
As árvores binomiais são normalmente implementadas com ponteiros ou referências entre
os nós. Esta abordagem tem a vantagem de que a estrutura de dados é dinâmica e, por
exemplo, pode-se facilmente extender a sua capacidade. Contudo este é também o facto
que penaliza mais a implementação dos amontoados baseados em árvores binomiais. Na
prática, a implementação dos amontoados binários sobre arrays é bastante mais eficiente,
não obstante a maior dificuldade em extender a sua capacidade. Seguindo algumas das
ideias propostas por Driscoll et al. [14], propõe-se aqui uma implementação dos amontoados
relaxados sobre arrays. Nos anexos A.1 e A.2 apresenta-se a implementação em Java.
A principal dificuldade tem a haver com a relação entre os ı́ndices do vector e os nós por
forma a aceder eficientemente aos descendentes e ao pai de cada nó. Seja n a capacidade
do amontoado. No que se segue, assume-se que os elementos são inteiros maiores ou iguais
a 0 e menores que n. Note-se que não existe perda de generalidade, visto que em geral
os elementos podem ser guardados num vector de dimensão n e o amontoado apenas tem
conhecimento dos ı́ndices. Neste caso, o grau máximo de cada nó é blog(n)c, excepto o
nó head . Como foi visto atrás o nó head pode ter blog(n)c + 1 filhos. Desta forma uma
abordagem consiste em representar cada nó como uma sequência de 2 + log(n) inteiros. O
amontoado será representado num vector com n ∗ (2 + blog(n)c) entradas cf. Figura 2.11.
Esta representação requer O(n log(n)) espaço.
parent
rank
child0
child1
childlog (n)
2
Figura 2.11. Representação de um amontoado sobre arrays, nomeadamente a representação de um nó.
2.3 Detalhes de Implementação
39
Seguindo uma sugestão proposta por Driscoll et al. [14] é possı́vel reduzir o espaço e
ainda assim obter uma implementação eficiente. Em vez de cada nó representar um elemento, cada nó passa a representar um conjunto ou grupo de elementos. Cada grupo terá
gn = dlog(n)e elementos no máximo. Portanto, o amontoado terá n/gn nós e a representação proposta requer O(n/gn log(n/gn)) espaço. Note-se que O((n/gn) log(n/gn)) =
O((n/ log(n))(log(n) − log(log(n))) = O(n − log(log(n))/ log(n)). Logo, o espaço neste caso
é linear em relação a n. É importante notar que agora cada nó tem de manter o ı́ndice do
menor elemento do grupo que representa cf. Figura 2.12.
min
parent
rank
child0
child1
childlog(n)
Figura 2.12. Representação de um amontoado sobre arrays, nomeadamente a representação de um nó, quando
cada nó representa um grupo de elementos.
O facto de cada nó representar gn elementos não interfere com o tempo das operações.
A diferença reside na forma como se encontra o mı́nimo, em particular quando se remove
o elemento com menor chave. Este é o único caso em que é necessário processar todos
os elementos de um grupo para encontrar o novo elemento com menor chave. Contudo,
uma vez que cada grupo tem O(log(n)) elementos, o tempo de procurar o novo elemento é
O(log(n)). Por outro lado, dado que cada nó é um inteiro e que cada elemento é também
um inteiro, pode-se mapear cada elemento para o nó a que pertence de forma eficiente.
Basta mapear o k-ésimo elemento para o nó k/gn. Logo, esta representação não influência
negativamente o tempo das operações.
No que diz respeito à gestão dos nós activos, no caso dos rank relaxed heaps basta
considerar um array de dimensão blog(n)c para guardar o nó activo em cada grau, se existir.
Note-se que na operação removeMin é necessário percorrer este array para actualizar o
nó com menor chave. Porém, dada a dimensão do array, o tempo da operação removeMin
mantém-se O(log(n)). No caso dos run relaxed heaps, a implementação da estrutura runsingleton sobre listas duplamente ligadas garante os tempos assimptóticos discutidos. É no
entanto importante relembrar que é necessário manter para cada nó a a referência para o
nó da lista em que a ocorre, caso ocorra em alguma das listas.
3
Filas com Prioridade
As filas com prioridade são utilizadas nas mais diversas aplicações. Por exemplo, em sistemas operativos, este tipo de dados abstracto é utilizado no escalonamento de processos
e de tarefas. Também na compressão de dados são utilizadas filas com prioridade, nomeadamente em conjunto com os códigos de Huffman. No área da inteligência artificial, o
algoritmo de procura A∗ também recorre a filas de prioridade. Outros exemplos de aplicação
são vários algoritmos em grafos, como o algoritmo de Dijkstra e o algoritmo de Prim. É
portanto importante definir o tipo de dados abstracto fila com prioridade, em particular a
interface a disponibilizar ao utilizador. No que se segue começa-se por discutir o tipo de
dados abstracto fila com prioridade e, em particular, a interface tı́pica a disponibilizar. Em
segundo lugar discute-se alguns detalhes de implementação.
3.1 Tipo de Dados Abstracto
Dado um conjunto de elementos que possuam uma chave, as operações mais comuns suportadas por este tipo de dados abstracto são: criar fila; inserir um novo elemento; remover
o elemento com maior prioridade; consultar o elemento com maior prioridade; remover
um elemento; aumentar a prioridade de um elemento; e juntar duas filas de prioridade.
Como referido anteriormente, neste trabalho considera-se que o elemento com menor chave
é o mais prioritário. Alternativamente, pode-se definir filas com prioridade em que o elemento com maior prioridade é o que tiver maior chave. Neste caso, a operação alternativa
à diminuição de chave será a de incrementação de chave.
A maior parte das bibliotecas apenas suporta parcialmente a implementação do tipo de
dados abstracto fila com prioridade, não suportando por exemplo a operação de aumentar a
prioridade de um elemento. Um exemplo desta situação é a classe PriorityQueue, definida
na Java Platform Standard Ed. 6. Esta classe apenas suporta, para além das operações
3.1 Tipo de Dados Abstracto
42
comuns de uma colecção, as operações de fila, i.e., as operações da interface Queue. Como
se pode observar na Figura 3.1, a interface Queue contém os seguintes métodos: poll, que
remove o elemento de maior prioridade; peek, que retorna o elemento de maior prioridade,
sem o remover; e offer, que insere um elemento na fila. Esta interface também contém
os métodos remove, element e add, que diferem dos outros em condições fronteira. Por
exemplo, o método add lança uma excepção quando o elemento não pode ser inserido
devido a restrições que possam existir na capacidade. Já no caso dos métodos remove e
element, estes lançam uma excepção caso a fila esteja vazia.
public interface Queue<E> extends Collection<E> {
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
}
Figura 3.1. A interface java.util.Queue.
Com as operações disponı́veis na interface Queue, se for necessário diminuir a chave
de um determinado elemento, este terá de ser removido, a sua chave alterada e inserido
novamente. Esta abordagem não é eficiente, especialmente em algoritmos como o de Dijkstra [1], em que o número de actualizações de chave é proporcional ao número de arcos no
grafo. É claro que é possı́vel implementar uma fila com prioridade sobre o tipo de dados
abstracto mapa ordenado, disponibilizado em quase todas as bibliotecas, como por exemplo
na Java Platform Standard Ed. 6. No entanto, o custo das operações insert, removeMin
e decreaseKey é O(log n), não garantindo os limites assimptóticos das estruturas de
dados mais avançadas para as operações insert e decreaseKey, como por exemplo os
amontoados relaxados.
Deste modo, de forma a estender o tipo de dados abstracto Queue, propõe-se a interface
PriorityQueue, definida na figura 3.2. Esta interface inclui o método update, o qual neste
trabalho apenas suportará a diminuição de chave. Como se pode observar na figura 3.2, o
método insert permite a inserção do elemento na fila com prioridade, retornando o ı́ndice
onde este foi inserido. O retorno do ı́ndice pode ser gerido pela aplicação que utilizar uma
implementação deste tipo de dados abstracto fila com prioridade, de modo a garantir que a
3.2 Detalhes de Implementação
43
operação update de um elemento não precisa de procurar por esse mesmo elemento. Visto
o método update receber como parâmetro o elemento e o ı́ndice, o utilizador pode, por
exemplo, encapsular no elemento o ı́ndice onde este ocorrer ou até definir um mapa que
a cada elemento faz corresponder um ı́ndice. A outra operação que é proposta é também
uma operação comum nas filas com prioridade, a operação de junção de duas filas.
public interface PriorityQueue<E> extends Queue<E> {
int insert(E e);
boolean update(int idx, E e);
boolean remove(int idx);
void meld(PriorityQueue<E> pq);
}
Figura 3.2. A interface PriorityQueue.
3.2 Detalhes de Implementação
Na implementação do tipo de dados abstracto PriorityQueue, realizada no contexto deste
trabalho, é utilizado um outro tipo de dados, nomeadamente o tipo de dados abstracto
amontoado, para a gestão das prioridades. A definição do amontoado como um tipo de
dados foi essencial para que a implementação realizada para o tipo de dados abstracto
fila com prioridade pudesse utilizar qualquer tipo de amontoado, como por exemplo os
amontoados binários ou os amontoados relaxados. A definição do tipo de dados abstracto
amontoado encontra-se na Figura 3.3.
public interface Heap{
public Comparator<Integer> comparator();
public void insert(int idx);
public void decreaseKey(int idx);
public void remove(int idx);
public int minimum();
public int removeMin();
}
Figura 3.3. A interface Heap.
3.2 Detalhes de Implementação
44
O tipo de dados abstracto amontoado não guarda os elementos da fila com prioridade,
apenas mantém a informação estritamente necessária para identificar os elementos. A implementação do tipo de dados abstracto fila com prioridade é que terá que os armazenar.
Deste modo, na implementação do tipo de dados fila com prioridade feita no contexto deste
trabalho, foi associada à fila um array, designado por store e definido internamente na
classe, onde se encontram os elementos. Nesta implementação, o amontoado identifica os
elementos pelos ı́ndices e mapeia-os para os nós internos do amontoado. Por exemplo, se
no topo do amontoado estiver o ı́ndice 3, significa que o elemento mais prioritário da fila se
encontra no ı́ndice 3 do array store. No entanto, poderia ter sido utilizada outra estrutura
que a cada elemento fizesse corresponder um inteiro distinto.
Ainda que o amontoado não contenha os elementos da fila com prioridade, as operações
realizadas sobre o mesmo necessitam de comparar a chave dos elementos, i.e., é necessário
existir um critério de comparação entre os elementos da fila com prioridade. Esse critério
de comparação terá então de ser fornecido através de um comparador que seja definido de
forma indirecta sobre os elementos da fila. Como se pode observar na Figura 3.3, o tipo
de dados abstracto amontoado contém o método comparator, que retorna o comparador
indirecto que está a ser utilizado.
Dado que o tipo de dados amontoado definido contém inteiros e que a cada elemento da
fila corresponde um inteiro distinto, um comparador indirecto pode ser definido da seguinte
forma: dados dois inteiros, o comparador retorna um inteiro que expressa uma ordem de
grandeza entre os elementos da fila identificados pelos os inteiros estão questão. No caso
concreto da implementação feita no contexto deste trabalho, esses inteiros correspondem
aos ı́ndices do array store.
Visto que os elementos estão armazenados num array, foi necessário considerar uma
estrutura auxiliar que contivesse os ı́ndices das posições livres desse mesmo array. Note-se
que, ao remover um dado elemento, a sua posição no array store fica disponı́vel. Deste
modo, para que se pudesse inserir um novo elemento sem recorrer a uma estrutura auxiliar,
ou ter-se-ia que procurar uma posição disponı́vel no array ou trocar de posição os elementos
do array, mantendo a sua ordem relativa. No entanto, ambas as operação seriam O(n) no
pior caso, em que n é o número de elementos desse mesmo array. Deste modo, optou-se
por utilizar um array auxiliar de ı́ndices livres, que permite, em tempo constante, obter
uma posição livre para realizar uma nova inserção.
4
Avaliação Experimental
Os amontoados relaxados garantem limites assimptóticos óptimos para as operações sobre amontoados, contudo na prática nem sempre se verificam melhores resultados. Com
vista a testar a implementação proposta para amontoados relaxados, realizaram-se várias
experiências. Em primeiro lugar testou-se a estrutura de dados com sequências de chaves
aleatórias e com diferentes taxas de inserção, actualização e remoção. Em segundo lugar
implementou-se o algoritmo de Dijkstra com os amontoados relaxados e realizaram-se várias
experiências com grafos de diferentes tamanhos e densidades. Discutem-se de seguida os
resultados obtidos. Ambas as implementações de amontoados relaxados são comparadas
com uma implementação eficiente de amontoados binários sobre vectores.
4.1 Sequências de Números Aleatórios
De forma a determinar em que situações os amontoados relaxados obtêm melhores resultados, realizaram-se vários testes em que o número de remoções e actualizações varia
face ao número de elementos no amontoado. A ideia consiste em inserir um conjunto com
n elementos no amontoado e de seguida realizar k iterações em que em cada iteração é
possı́vel actualizar uma chave com probabilidade pu ou remover o elemento com menor
chave com probabilidade pr . A motivação para esta formulação tem a haver com o objectivo de comparar o impacto do número das operações, em particular quando o número de
actualizações é elevado ou quando nem todos os elementos têm de ser removidos. Note-se
que é comum em problemas de anexação preferencial em grafos utilizar-se um fila com
prioridades para guardar os arcos e não ser necessário removerem-se todos. Normalmente
o algoritmo termina quando os vértices estão todos ligados, o que obviamente não implica
considerar todos os arcos.
4.1 Sequências de Números Aleatórios
46
O primeiro teste consistiu apenas em inserir elementos num amontoado. Na Figura 4.1
verifica-se que ambas as implementações de amontoados relaxados obtêm tempos idênticos
e que os amontoados binários obtêm melhores resultados para os valores de n considerados,
0 ≤ n ≤ 200000. Contudo, considerando valores de n superiores como na Tabela 4.1, os
amontoados relaxados demonstram melhores resultados. Este facto é consistente com os
limites assimptóticos teóricos e com as constantes multiplicativas devidas à complexidade
dos amontoados relaxados.
Após a inserção de n elementos, no segundo teste removeu-se o nó com a menor chave
até o amontoado ficar vazio. Na Figura 4.2 apresentam-se as estatı́sticas deste teste. É
importante notar que os tempos apresentados reflectem apenas as remoções, não contabilizando a inserção dos elementos. Neste caso os amontoados binários obtêm novamente
melhores tempos. Porém a diferença para os amontoados relaxados é menos significativa
que no caso da inserção.
Nos terceiro e quarto testes, Figuras 4.3 e 4.4, avaliou-se a eficiência das implementações
quando o número de actualizações é superior a n e superior ao número de remoções. Na
Figura 4.3 o número de actualizações é dez vezes o número de elementos no amontoado,
i.e., pu = 1.0 e k = 10n. Na Figura 4.4 o número de actualizações é cem vezes o número
de elementos no amontoado, i.e., pu = 1.0 e k = 100n. Como era esperado, quanto maior
o número de actualizações, melhor se comportam os amontoados relaxados.
Embora os testes descritos até ao momento mostrem que a implementação proposta para
os amontoados relaxados é eficiente e consistente com os limites assimptóticos teóricos,
não se observou um ganho significativo em relação aos amontoados binários. Na Tabela
4.1 apresentam-se resultados em que o número de elementos é da ordem dos 50 milhões. O
número de iterações nos três primeiros testes é 200 milhões e em cada iteração ocorre uma
actualização, pu = 1.0. O número de extracções do elemento com menor chave varia, i.e.,
consideram-se diferentes valores para pr . Mesmo para um número elevado de elementos
a diferença em relação aos amontoados binários não é significativa, embora os resultados
mostrem que os amontoados relaxados têm neste caso melhores resultados. Portanto, para
grandes volumes de dados, os amontoados relaxados não só são eficientes como devem
obter melhores resultados que os amontoados binários. É também importante referir que
a implementação proposta para os amontoados relaxados é eficiente do ponto de vista
de memória, requerendo significativamente menos memória. O último teste da Tabela 4.1
4.1 Sequências de Números Aleatórios
0.30
47
binary heap
rank relaxed heap
run relaxed heap
0.25
seg.
0.20
0.15
0.10
0.05
0.00
0
50000
100000
n
150000
200000
Figura 4.1. Tempo de inserção de n elementos no amontoado. Os valores correspondem à média de 10 execuções
por implementação.
0.80
binary heap
rank relaxed heap
run relaxed heap
0.70
0.60
seg.
0.50
0.40
0.30
0.20
0.10
0.00
0
50000
100000
n
150000
200000
Figura 4.2. Tempo de remoção de todos os n elementos no amontoado. Os valores correspondem à média de 10
execuções por implementação.
4.1 Sequências de Números Aleatórios
1.80
48
binary heap
rank relaxed heap
run relaxed heap
1.60
1.40
seg.
1.20
1.00
0.80
0.60
0.40
0.20
0.00
0
50000
100000
n
150000
200000
Figura 4.3. Tempo de actualização e remoção num amontoado com n elementos, em que o número de iterações
m é igual a 10n, a probabilidade de actualização pu é 1.0 e a probabilidade de remoção pr é 0.05. Os valores
correspondem à média de 10 execuções por implementação.
binary heap
rank relaxed heap
run relaxed heap
10.00
seg.
8.00
6.00
4.00
2.00
0.00
0
50000
100000
n
150000
200000
Figura 4.4. Tempo de actualização e remoção num amontoado com n elementos, em que o número de iterações
m é igual a 100n, a probabilidade de actualização pu é 1.0 e a probabilidade de remoção pr é 0.005. Os valores
correspondem à média de 10 execuções por implementação.
4.2 Algoritmo de Dijkstra
49
pretende aferir em que condições os run relaxed heaps obtêm melhores resultados que os
rank relaxed heaps. Neste teste são apenas feitas 200000 iterações e, em cada iteração, é
feita uma actualização e uma extracção do nó com menor chave. Observa-se portanto que
os run relaxed heaps apenas se justificam em situações em que o número de actualizações é
baixo ou em que é necessária a garantia que as actualizações são feitas em tempo constante.
Tabela 4.1. Estatı́sticas para um amontoado com 50 × 106 elementos. Neste caso cada elemento é um real e
é guardado num vector auxiliar key. Legenda: k é o número de iterações; pu é a probabilidade de ocorrer uma
actualização; pr é a probabilidade de ocorrer uma remoção; Ti é o tempo de inserção dos elementos em segundos;
T é o tempo das k iterações onde podem ocorrer actualizações e remoções em segundos; M é a memória em MB.
Implementação
binary
rank relaxed
run relaxed
binary
rank relaxed
run relaxed
binary
rank relaxed
run relaxed
binary
rank relaxed
run relaxed
k
6
200 × 10
200 × 106
200 × 106
200 × 106
200 × 106
200 × 106
200 × 106
200 × 106
200 × 106
200 × 103
200 × 103
200 × 103
pu
pr
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
0.0001
0.0001
0.0001
0.001
0.001
0.001
0.25
0.25
0.25
1.0
1.0
1.0
Ti (seg.) T (seg.) M (MB)
9.985
7.734
7.766
9.985
7.734
7.766
9.985
7.734
7.766
9.985
7.734
7.766
228.871
195.515
206.031
230.075
196.319
208.896
624.432
383.578
606.622
1.840
1.617
1.563
1736
1316
1357
1736
1316
1357
1736
1316
1357
1736
1316
1357
4.2 Algoritmo de Dijkstra
O algoritmo de Dijkstra [1] para determinar caminhos mais curtos num grafo é, provavelmente, o exemplo mais conhecido em que a implementação da fila com prioridade é
determinante para a eficiência do algoritmo. Para detalhes a respeito do algoritmo pode-se
consultar, por exemplo, o livro de introdução aos algoritmos por Cormen et al. [22]. O
ponto importante para a análise aqui realizada é o facto de que, para um grafo com n
vértices e m arcos, uma implementação do algoritmo de Dijkstra com amontoados binários
requer tempo O(n log(n) + m log(n)), no pior caso, para determinar os caminhos mais curtos a partir de um dado vértice fonte, enquanto que uma implementação com amontoados
relaxados requer tempo O(n log(n) + m). Porém, na prática, dada a complexidade dos
4.2 Algoritmo de Dijkstra
50
amontoados relaxados, é difı́cil conseguir melhores tempos. Note-se que nos amontoados
relaxados, embora algumas operações decorram em tempo constante, as constantes multiplicativas são mais elevadas que no caso dos amontoados binomiais. Por outro lado o
logaritmo é uma função monótona crescente, com a primeira derivada a convergir para 0
quando n → ∞ e com a segunda derivada negativa. Logo, as constantes multiplicativas
elevadas podem conduzir a piores resultados mesmo para conjuntos de dados de dimensão
razoável.
Neste estudo efectuaram-se duas avaliações com o algoritmo de Dijkstra. Na primeira
avaliação foram gerados grafos aleatórios segundo o modelo de duplicação [23], um modelo
que reflecte muitas das propriedades das redes reais, e.g., redes sociais. Dado um grafo não
dirigido G0 = (V0 , E0 ) e uma probabilidade 0 ≤ p ≤ 1, o modelo de duplicação permite
construir recursivamente um grafo dirigido Gt = (V, E) por duplicação parcial da seguinte
forma:
1. Gt = Gt−1 e selecciona-se aleatoriamente um vértice u ∈ Vt−1 ;
2. adiciona-se um novo vértice e um novo arco u, v a Gt ;
3. para cada vizinho w de u em Gt−1 , adiciona-se o arco (v, w) a Gt com probabilidade p.
Os arcos adicionados no passo 2 fazem com que o grafo seja sempre ligado. Usualmente, G0
é um grafo constituı́do apenas por um vértice e, no passo t, Gt terá t + 1 vértices. Chung
et al. [23] provaram que, com p → 1 e n → ∞, o modelo de duplicação gera grafos em que
distribuição dos graus dos vértices é exponencial com expoente β tal que
p(β − 1) = 1 − pβ−1 .
(4.1)
Em particular, se 21 < p < 1, então β < 2. Porém, os valores de β interessantes, entre
1 e 2, são obtidos apenas com probabilidades 0.5 < p < 0.56714329.... No seguimento
considerar-se-á p = 0.5. Os pesos para os arcos foram gerados aleatoriamente entre 0 e 100.
Na segunda avaliação foram gerados grafos completos, i.e., cliques, com pesos aleatórios.
Portanto, o número de arcos é n(n − 1)/2 em que n é o número de vértices. Os pesos dos
arcos tomam também valores entre 0 e 100.
Os resultados obtidos mostram que a implementação proposta é competitiva na prática,
com resultados comparáveis aos amontoados binários e, no caso dos grafos gerados com o
modelo de duplicação, com melhores resultados. Para grafos maiores, os ganhos deverão
ser ainda mais notórios. É importante referir que no caso dos grafos obtidos por duplicação
4.2 Algoritmo de Dijkstra
30.0
51
binary heap
rank relaxed heap
run relaxed heap
25.0
seg.
20.0
15.0
10.0
5.0
0.0
0
50000
100000
n
150000
200000
Figura 4.5. Tempo de execução do algoritmo de Dijkstra para grafos com n vértices gerados a partir do modelo
de duplicação com p = 0.5. Os valores correspondem à média de 10 execuções por implementação.
2.0
binary heap
rank relaxed heap
run relaxed heap
seg.
1.5
1.0
0.5
0.0
0
1000
2000
3000
4000
n
5000
6000
7000
8000
Figura 4.6. Tempo de execução do algoritmo de Dijkstra para grafos completos com n vértices. Os valores
correspondem à média de 10 execuções por implementação.
4.2 Algoritmo de Dijkstra
52
o número de arcos é significativamente maior que o número de vértices, e.g., os grafos com
200000 vértices têm cerca de 30 milhões de arcos.
5
Conclusão
Neste trabalho estudou-se a implementação eficiente de filas com prioridade, um tipo de
dados abstracto com inúmeras aplicações. De um modo geral, as implementações mais
eficientes têm por base a estrutura de dados amontoado. Nos últimos anos surgiram vários
tipos de amontoados que melhoram os limites assimptóticos para o tempo das operações.
Contudo, os amontoados binários continuam a ser os mais utilizados na prática. Este
facto deve-se a que as alternativas são bastante complexas e difı́ceis de implementar, em
parte porque as estruturas mais complexas implicam constantes multiplicativas elevadas.
No presente estudo dá-se uma implementação eficiente de duas variantes de amontoados
com limites assimptóticos inferiores aos dos amontoados binários e, ainda que complexos,
competitivos na prática.
As variantes estudadas são os amontoados relaxados propostos por Driscoll et al. [14],
nomeadamente os rank relaxed heaps e os run relaxed heaps. Os run relaxed heaps foram
a primeira variante a suportar a operação decreaseKey em tempo constante no pior
caso, o que não acontece com os amontoados binários, que suportam esta operação em
tempo O(log(n)) no pior caso, com n o número de elementos no amontoado. O estudo
consistiu na análise detalhada das estruturas de dados, das operações e dos requisitos
a nı́vel de tempo e espaço necessários. Como resultado conseguiu-se uma implementação
eficiente, quer ao nı́vel de tempo quer ao nı́vel de espaço. A avaliação experimental permitiu
concluir que, na prática, a implementação proposta é competitiva com os amontoados
binários, conseguindo melhores resultados para grandes conjuntos de dados. Discutiu-se
ainda a implementação de filas com prioridade tendo por base os amontoados relaxados,
incluindo a operação diminuição de chave em tempo constante. Esta operação é inexistente
em muitas implementações de filas com prioridade disponı́veis em bibliotecas de uso geral.
A implementação foi desenvolvida em Java e encontra-se em anexo.
5 Conclusão
54
No estudo realizado conclui-se que uma implementação cuidada de amontoados relaxados é competitiva. O facto de não existirem implementações eficientes tem sido o principal
obstáculo para adopção na prática deste tipo de estruturas de dados. É importante referir
que a implementação proposta pode ainda ser melhorada, em particular utilizando técnicas
mais recentes que permitem, por exemplo, reduzir o número de comparações. É no entanto
necessário uma análise cuidada destas técnicas, pois implicam em geral o uso de estruturas
de dados mais complexas e, portanto, é necessário avaliá-las ao nı́vel da implementação.
Este estudo contribui ainda com uma exposição completa das estruturas de dados e
operações associadas aos amontoados relaxados. A maior parte dos livros inclui amontoados
binários e, apenas alguns, incluem os amontoados binomiais ou os amontoados de Fibonacci.
Não é do conhecimento da autora um livro que inclua ou discuta os amontoados relaxados.
Note-se que estes são considerados uma das estruturas de dados mais promissoras nesta área
e, portanto, com interesse pedagógico em disciplinas de algoritmia e estruturas de dados.
Em particular é importante estudar as implicações em muitos algoritmos bem conhecidos.
Referências
1. Dijkstra, E.W.: A note on two problems in connexion with graphs. In Numerische Mathematik 1 (1959)
269–271
2. Prim, R.C.: Shortest connection networks and some generalizations. Bell System Technical Journal 36 (1957)
1389–1401
3. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall (2001)
4. Williams, J.: Algorithm 232 (heap sort). Commun. ACM 7 (1964) 347–348
5. Mendelson, R., Tarjan, R.E., Thorup, M., Zwick, U.: Melding priority queues. In Hagerup, T., Katajainen, J.,
eds.: SWAT. Volume 3111 of Lecture Notes in Computer Science., Springer (2004) 223–235
6. Vuillemin, J.: A data structure for manipulating priority queues. Commun. ACM 21(4) (1978) 309–315
7. Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms.
In: FOCS, IEEE (1984) 338–346
8. Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J.
ACM 34(3) (1987) 596–615
9. Tarjan, R.: Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods 6 (1985)
306–318
10. Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: A new form of self-adjusting
11.
12.
13.
14.
heap. Algorithmica 1(1) (1986) 111–129
Pettie, S.: Towards a final analysis of pairing heaps. In: FOCS, IEEE Computer Society (2005) 174–183
Fredman, M.L.: On the efficiency of pairing heaps and related data structures. J. ACM 46(4) (1999) 473–501
Elmasry, A.: Pairing heaps with (o(log log ) decrease cost. In Mathieu, C., ed.: SODA, SIAM (2009) 471–476
Driscoll, J.R., Gabow, H.N., Shrairman, R., Tarjan, R.E.: Relaxed heaps: An alternative to fibonacci heaps
with applications to parallel computation. Commun. ACM 31(11) (1988) 1343–1354
15. Brodal, G.S.: Worst-case efficient priority queues. In: SODA ’96: Proceedings of the seventh annual ACM-SIAM
symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics
(1996) 52–58
16. Elmasry, A., Jensen, C., Katajainen, J.: Two-tier relaxed heaps. Acta Inf. 45(3) (2008) 193–210
17. Kaplan, H., Tarjan, R.E.: Thin heaps, thick heaps. ACM Transactions on Algorithms 4(1) (2008)
18. Moret, B., Shapiro, H.: A general technique for implementation of efficient priority queues. 3rd Israel Symposium on the Theory of Computing Systems (1995) 57–66
19. Peterson, G.: A balanced tree scheme for meldable heaps with updates. Technical report, School of Information
and Computer Science, Georgia Institute of Technology (1987)
20. Takaoka, T.: Theory of 2-3 heaps. Discrete Applied Mathematics 126(1) (2003) 115–128
21. Elmasry, A.: Layered heaps. In Hagerup, T., Katajainen, J., eds.: SWAT. Volume 3111 of Lecture Notes in
Computer Science., Springer (2004) 212–222
Referências
118
22. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press (2001)
23. Chung, F., Lu, L., Dewey, T.G., Galas, D.J.: Duplication models for biological networks. Journal of Computational Biology 10(5) (2003) 677–687