Estruturas de dados - Algoritmos: Notas e Compilações

Filas de prioridade¶

Uma fila de prioridades é uma estrutura de dados abstrata (TAD — Tipo Abstrato de Dados) que mantém um conjunto de elementos, cada um associado a uma chave (prioridade). Os elementos podem ser inseridos e removidos do conjunto, sendo que a operação de remoção sempre extrai o elemento com menor chave (elemento mínimo).

Interface da fila de prioridades¶

O TAD fila de prioridades oferece as seguintes operações:

make-priority-queue(): cria uma fila vazia.
build-priority-queue(S): constrói uma fila a partir de um conjunto $S$ de $n$ elementos onde cada elemento já possui sua chave associada. Útil para inicialização eficiente em algoritmos como Prim e Dijkstra.
insert(Q, x, k): insere o elemento $x$ com chave $k$ na fila.
extract-min(Q): remove e retorna o elemento de menor chave da fila.
decrease-key(Q, x, k): diminui a chave do elemento $x$ para $k$ (supõe-se que $k$ é menor que a chave atual).
x in Q: testa se o elemento $x$ está presente na fila.

A seguir, apresentamos duas implementações dessa interface, mostrando como a escolha afeta a complexidade dos algoritmos que as utilizam.

Implementação com arranjo simples¶

A implementação mais direta de uma fila de prioridades é usar um arranjo dinâmico, onde cada entrada é um par (element, key):

element: o objeto armazenado (ex: um vértice de um grafo)
key: a chave (prioridade) associada ao objeto

Quando acessamos Q[i], obtemos um par. Para extrair o elemento, usamos Q[i].element; para acessar a chave, Q[i].key.

Para suportar as operações eficientemente, mantemos dois arrays auxiliares:

pos[x]: posição (índice) do elemento $x$ no arranjo da fila
inQ[x]: boolean indicando se $x$ está na fila (para testes rápidos de membros)

Dessa forma, operações como membros e atualização de chave têm acesso direto (O(1)) ao elemento.

Pseudocódigo para arranjo simples¶

build-priority-queue(S)
// argumentos:
// S: conjunto de n elementos com chaves já atribuídas

  Q.size = n
  for i = 1 to n
    Q[i] = (S[i], S[i].key)
    pos[S[i]] = i
    inQ[S[i]] = true
  return Q

insert(Q, x, k)
// argumentos:
// Q: fila de prioridades (arranjo)
// x: elemento a inserir
// k: chave do elemento

  Q.size = Q.size + 1
  Q[Q.size] = (x, k)
  pos[x] = Q.size
  inQ[x] = true

member(Q, x)
// argumentos:
// Q: fila
// x: elemento

  return inQ[x]

decrease-key(Q, x, k)
// argumentos:
// Q: fila
// x: elemento
// k: nova chave (menor que a atual)

  i = pos[x]
  Q[i].key = k

extract-min(Q)
// argumentos:
// Q: fila

  min_index = 1
  for i = 2 to Q.size
    if Q[i].key < Q[min_index].key
      min_index = i
  x = Q[min_index].element
  Q[min_index] = Q[Q.size]
  pos[Q[min_index].element] = min_index
  inQ[x] = false
  Q.size = Q.size - 1
  return x

Análise de complexidade¶

Operação	Custo
build-priority-queue	$O(n)$
insert	$O(1)$
member	$O(1)$
decrease-key	$O(1)$
extract-min	$O(n)$

Complexidade de tempo (build-priority-queue): $\Theta(n)$ , pois inicializa todos os $n$ elementos uma vez.
Complexidade de tempo (extract-min): $\Theta(n)$ , pois realiza uma varredura linear sobre os elementos restantes para encontrar o mínimo.
Complexidade de espaço: $\Theta(n)$ para armazenar os $n$ elementos e os arrays auxiliares pos e inQ.

Implementação com heap binário mínimo¶

Um heap binário é uma estrutura de dados que mantém uma propriedade de ordem em uma árvore binária implícita (representada como um arranjo contíguo). Especificamente, um min-heap satisfaz: o valor de cada nó é menor ou igual ao valor de seus filhos. Essa propriedade garante que o elemento mínimo sempre está na raiz (posição 1 do arranjo).

As operações da TAD são implementadas de forma especializada nesta estrutura, com prefixo heap- para distinguir a implementação concreta:

build-priority-queue → heap-build (construção eficiente em $\Theta(n)$ )
insert → heap-insert (inserção com sift-up, $O(\log n)$ )
decrease-key → heap-decrease-key (diminuição com sift-up, $O(\log n)$ )
extract-min → heap-extract-min (extração com min-heapify, $O(\log n)$ )
x in Q usa o array inQ (O(1), conforme na TAD)

Estrutura da implementação¶

Assim como na implementação com arranjo simples, cada entrada no heap é um par (element, key). O heap armazena esses pares em um arranjo contíguo, mantendo a propriedade de min-heap nas chaves.

Mantemos dois arrays auxiliares para suportar as operações:

pos[x]: posição (índice) do elemento $x$ no heap
inQ[x]: boolean indicando se $x$ está na fila (para testes rápidos de membros)

Adicionalmente, temos:

size: número de elementos atualmente no heap

Com esses auxiliares, operações como x in Q, heap-decrease-key e heap-extract-min conseguem manter a eficiência.

Estrutura e acesso na árvore binária implícita¶

Para um nó na posição $i$ do arranjo:

parent(i)
// argumentos:
// i: índice no arranjo

  return floor(i / 2)

left(i)
// argumentos:
// i: índice no arranjo

  return 2 * i

right(i)
// argumentos:
// i: índice no arranjo

  return 2 * i + 1

Pseudocódigo para heap binário mínimo¶

min-heapify(Q, i)
// argumentos:
// Q: arranjo (heap)
// i: índice do nó a restaurar a propriedade de min-heap

  l = left(i)
  r = right(i)
  smallest = i
  if l <= Q.size and Q[l].key < Q[i].key
    smallest = l
  if r <= Q.size and Q[r].key < Q[smallest].key
    smallest = r
  if smallest != i
    swap(Q, i, smallest)
    pos[Q[i].element] = i
    pos[Q[smallest].element] = smallest
    min-heapify(Q, smallest)

heap-build(S)
// argumentos:
// S: conjunto de n elementos com chaves já atribuídas
// implementação heap da operação TAD build-priority-queue

  Q.size = n
  for i = 1 to n
    Q[i] = (S[i], S[i].key)
    pos[S[i]] = i
    inQ[S[i]] = true
  for i = floor(n / 2) down to 1
    min-heapify(Q, i)

Assim como no heapsort (capítulo de ordenação), a construção de um heap a partir de um arranjo arbitrário custa $\Theta(n)$ , apesar dos muitos chamamentos recursivos ao min-heapify. Isso porque a maioria dos nós está próxima das folhas (altura pequena) e realiza pouquíssimas comparações.

heap-insert(Q, x, k)
// argumentos:
// Q: heap
// x: elemento a inserir
// k: chave inicial
// implementação heap da operação TAD insert

  Q.size = Q.size + 1
  i = Q.size
  Q[i] = (x, k)
  pos[x] = i
  inQ[x] = true
  while i > 1 and Q[parent(i)].key > Q[i].key
    swap(Q, i, parent(i))
    pos[Q[i].element] = i
    pos[Q[parent(i)].element] = parent(i)
    i = parent(i)

Diferentemente de heap-build, que constrói eficientemente em $O(n)$ a partir de elementos com chaves já atribuídas, heap-insert adiciona um único elemento com uma chave especificada.

heap-decrease-key(Q, x, k)
// argumentos:
// Q: heap
// x: elemento
// k: nova chave (menor que a atual)
// implementação heap da operação TAD decrease-key

  i = pos[x]
  Q[i].key = k
  while i > 1 and Q[parent(i)].key > Q[i].key
    swap(Q, i, parent(i))
    pos[Q[i].element] = i
    pos[Q[parent(i)].element] = parent(i)
    i = parent(i)

heap-extract-min(Q)
// argumentos:
// Q: heap
// implementação heap da operação TAD extract-min

  x = Q[1].element
  Q[1] = Q[Q.size]
  pos[Q[1].element] = 1
  inQ[x] = false
  Q.size = Q.size - 1
  if Q.size > 0
    min-heapify(Q, 1)
  return x

Análise de complexidade¶

Operação (TAD)	Implementação heap	Custo
build-priority-queue	heap-build	$O(n)$
insert	heap-insert	$O(\log n)$
x in Q	(array `inQ`)	$O(1)$
decrease-key	heap-decrease-key	$O(\log n)$
extract-min	heap-extract-min	$O(\log n)$

Complexidade de tempo (heap-build): $\Theta(n)$ , análise idêntica ao capítulo de ordenação.
Complexidade de tempo (min-heapify): $O(\log n)$ , proporcional à altura da árvore binária.
Complexidade de tempo (heap-decrease-key e heap-insert): $O(\log n)$ por causa do sift-up.
Complexidade de tempo (heap-extract-min): $O(\log n)$ por causa do min-heapify.
Complexidade de espaço: $\Theta(n)$ para armazenar os $n$ elementos e o array pos.

Comparação de implementações¶

Operação TAD	Arranjo simples	Heap binário
build-priority-queue	$O(n)$	heap-build: $O(n)$
insert	$O(1)$	heap-insert: $O(\log n)$
x in Q	$O(1)$	$O(1)$
decrease-key	$O(1)$	heap-decrease-key: $O(\log n)$
extract-min	$O(n)$	heap-extract-min: $O(\log n)$

A escolha entre arranjo simples e heap depende do padrão de operações. Se o algoritmo realiza muitas operações extract-min e decrease-key, o heap é preferível (operações logarítmicas). Se as operações decrease-key são raras e dominam extract-min, o arranjo simples pode ser mais eficiente (operações constantes para aquelas operações).

Conjuntos disjuntos¶

Estrutura de dados abstrata (TAD) que mantém uma coleção de conjuntos dinâmicos disjuntos dois a dois: cada elemento pertence a no máximo um conjunto. Cada conjunto é identificado por um representante — um de seus próprios membros, que funciona como o “nome” do conjunto nas consultas. O representante só perde essa função quando seu conjunto é fundido a outro.

Os conjuntos disjuntos são base para algoritmos sobre grafos como o Kruskal (capítulo de grafos): para cada aresta, o algoritmo testa se as extremidades já pertencem à mesma componente com find-set e, se não, une as duas componentes com union. Outras aplicações clássicas incluem o cálculo de componentes conexas e a detecção de ciclos.

Interface dos conjuntos disjuntos¶

O TAD de conjuntos disjuntos oferece as seguintes operações:

make-set(x): cria um novo conjunto contendo apenas o elemento $x$ (que ainda não pertence a nenhum outro conjunto).
union(x, y): funde em um único conjunto os conjuntos que contêm $x$ e $y$ .
find-set(x): retorna o representante do conjunto (único) que contém $x$ .

Implementação com listas ligadas¶

Cada conjunto é representado por uma lista ligada de seus elementos. Um objeto de conjunto aponta para o primeiro elemento da lista (head), para o último (tail) e mantém o tamanho da lista (length). Cada elemento $x$ , por sua vez, aponta para o próximo da lista (x.next) e de volta para o objeto do conjunto a que pertence (x.set). O representante é o primeiro elemento da lista, apontado por head.

find-set(x) segue o ponteiro x.set e devolve head: tempo constante.
union(x, y) emenda a lista de $y$ no fim da lista de $x$ e reescreve o ponteiro set de cada elemento absorvido.

Pseudocódigo para listas ligadas (encadeada)¶

make-set(x)
// argumentos:
// x: elemento a colocar em um novo conjunto unitário

  S = new set-object
  S.head = x
  S.tail = x
  S.length = 1    // usado apenas pela heurística de união ponderada
  x.next = NIL
  x.set = S

find-set(x)
// argumentos:
// x: elemento cujo conjunto queremos identificar

  return x.set.head    // o representante é o primeiro elemento da lista

union(x, y)
// argumentos:
// x: elemento do primeiro conjunto
// y: elemento do segundo conjunto

  S_x = x.set
  S_y = y.set
  if S_x == S_y
    return    // já estão no mesmo conjunto; nada a fazer
  S_x.tail.next = S_y.head    // emenda a lista de y no fim da lista de x
  S_x.tail = S_y.tail
  z = S_y.head
  while z != NIL
    z.set = S_x    // os elementos absorvidos passam a apontar para o conjunto de x
    z = z.next

Análise de complexidade¶

Operação	Custo
make-set	$O(1)$
find-set	$O(1)$
union	$O(n)$

Complexidade de tempo (union): proporcional ao comprimento da lista anexada, pois cada elemento absorvido precisa do ponteiro set reescrito; $\Theta(n)$ no pior caso.
Complexidade de espaço: $\Theta(n)$ : um nó com next e set por elemento, mais um objeto de conjunto por coleção.

Uma heurística clássica reduz ainda mais o custo das fusões: a união ponderada usa o atributo length para anexar sempre a lista menor ao fim da maior. Assim, o ponteiro de um elemento só é reescrito quando o conjunto que o contém pelo menos dobra de tamanho — e um conjunto dobra no máximo $\log_2 n$ vezes. Logo, cada elemento tem seu ponteiro reescrito no máximo $\lfloor \log_2 n \rfloor$ vezes em toda a execução.

Isso motiva uma forma útil de medir custos: o custo amortizado de uma operação é a média do custo total de uma sequência de operações — e não o pior caso de uma operação isolada. Uma fusão isolada pode até ser cara, desde que a média das demais fique baixa. Considerando uma sequência de $m$ operações sobre no máximo $n$ elementos (cada um criado por um make-set), a união ponderada garante custo total $O(m + n \log n)$ : um custo amortizado de $O(\log n)$ por operação.

As listas mantêm find-set em tempo constante, mas as fusões ainda reescrevem ponteiros de muitos elementos. A implementação a seguir atinge custo quase constante amortizado para todas as operações, representando cada conjunto como uma árvore com raiz.

Implementação com florestas com ponteiros¶

Cada conjunto é representado por uma árvore com raiz, em uma floresta. Cada elemento $x$ é um nó com um atributo-ponteiro x.p para seu pai; a raiz aponta para si mesma e é o representante do conjunto. Assim:

find-set(x) sobe a cadeia de pais x.p, x.p.p, ... até alcançar a raiz.
union(x, y) localiza as duas raízes e pendura uma sob a outra (a ligação em si é feita pela auxiliar link).

Sem cuidado, a floresta degenera: se link sempre pendura a mesma árvore sob a outra, uma sequência de fusões produz uma árvore-caminho de altura $\Theta(n)$ , e find-set passa a custar $\Theta(n)$ . Duas otimizações clássicas resolvem isso.

Union by rank e path compression¶

Union by rank: cada nó mantém um rank, um limitante superior para a altura de sua subárvore. Ao fundir duas árvores, a raiz de menor rank aponta para a raiz de maior rank; em caso de empate, uma das raízes vira a nova raiz e tem o rank incrementado. Como a altura só cresce quando fundimos árvores de mesma altura, ela fica limitada a $O(\log n)$ .
Path compression: durante find-set(x), após alcançar a raiz, todos os nós visitados no caminho passam a apontar diretamente para ela. Cada consulta achata a árvore, encurtando as buscas futuras.

Cada heurística isoladamente já melhora o desempenho; juntas, o custo amortizado por operação (a média do custo total de uma sequência) cresce tão lentamente com $n$ que, na prática, é como se fosse constante: tempo quase constante amortizado.

Pseudocódigo para florestas com rank e compressão de caminho¶

O pseudocódigo a seguir já incorpora as duas otimizações: make-set inicializa o rank, link aplica union by rank e find-set aplica a compressão de caminho.

make-set(x)
// argumentos:
// x: elemento a colocar em um novo conjunto unitário

  x.p = x      // a árvore nova tem um único nó, que é a própria raiz
  x.rank = 0   // subárvore de altura zero

union(x, y)
// argumentos:
// x: elemento do primeiro conjunto
// y: elemento do segundo conjunto

  link(find-set(x), find-set(y))

link(x, y)
// argumentos:
// x: raiz da árvore do primeiro conjunto
// y: raiz da árvore do segundo conjunto
// une as duas árvores seguindo union by rank

  if x.rank > y.rank
    y.p = x    // a árvore mais baixa é pendurada sob a mais alta
  else
    x.p = y
    if x.rank == y.rank
      y.rank = y.rank + 1    // alturas iguais: a árvore resultante cresce uma unidade

find-set(x)
// argumentos:
// x: elemento cujo conjunto queremos identificar

  if x != x.p    // não é a raiz?
    x.p = find-set(x.p)    // a raiz vira o pai (path compression)
  return x.p    // retorna a raiz

Análise de complexidade¶

Operação	Custo amortizado
make-set	$O(1)$
union	quase constante
find-set	quase constante

Complexidade de tempo (sequência de operações): uma sequência de $m$ operações sobre no máximo $n$ elementos (cada um criado por um make-set) tem custo total essencialmente linear -- o custo amortizado por operação é constante na prática.
Complexidade de espaço: $\Theta(n)$ para os nós com os atributos p e rank.