Estruturas avançadas

Heap, união-busca, deque e contador — o que cada uma custa, e o problema que só ela resolve bem.

Cluster e vault resolvem quase tudo. As quatro estruturas desta página existem para os casos em que eles obrigam a pagar O(n) por algo que podia ser O(log n) ou O(1) — e todas já vêm em `Arcane.Collections`.

Heap — o menor primeiro, em `O(log n)`#

Uma fila de prioridade. O que ela dá, e o cluster não: inserir e tirar o menor mantendo a ordem sem ordenar a lista inteira.

adopt Arcane.Collections as C

h := C.heap([5, 1, 9, 3])
C.heap_push(h, 2)
out C.heap_peek(h)     // 1  — o menor, sem remover
out C.heap_pop(h)      // 1
out C.heap_pop(h)      // 2

Onde isso decide: os k maiores#

Ordenar tudo para pegar 10 é O(n log n). Um heap de tamanho 10 é O(n log k) — e com k pequeno, log k é praticamente uma constante:

adopt Arcane.Collections as C
adopt Arcane.Time as T

dados := [randint(1, 1000000) cycle i in range(0, 300000)]

inicio := T.monotonic()
maiores_a := sorted(dados)[len(dados) - 10:]
ms_sort := (T.monotonic() - inicio) * 1000

inicio := T.monotonic()
maiores_b := C.top_n(dados, 10)
ms_heap := (T.monotonic() - inicio) * 1000

out $"ordenar tudo e cortar 10:  {round(ms_sort, 1)} ms"
out $"top_n com heap de 10:      {round(ms_heap, 1)} ms"

ordenar tudo e cortar 10:  25.7 ms
top_n com heap de 10:      1.7 ms

15x, e a distância cresce com n. C.top_n e C.bottom_n fazem isso; C.priority_queue é o mesmo mecanismo com prioridade explícita, que é como se escreve um Dijkstra ou um escalonador.

União-busca — "estes dois estão no mesmo grupo?"#

O problema: juntar elementos em grupos e perguntar se dois estão juntos. Com listas, cada pergunta varre tudo; a união-busca responde em tempo quase constante.

adopt Arcane.Collections as C

uf := C.union_find(["a", "b", "c", "d"])
uf.union("a", "b")
uf.union("c", "d")
out uf.connected("a", "b")     // yes
out uf.connected("a", "c")     // no
out uf.count()                 // 2 grupos

A compressão de caminho é o que dá o amortizado: cada busca achata a árvore que percorreu, e a próxima passa direto. É o mesmo raciocínio da análise amortizada do append — a operação cara paga pelas baratas que vêm depois.

Serve para componentes conexos de um grafo, para detectar ciclo ao montar uma árvore geradora mínima, e para agrupar duplicatas — "este e-mail e este telefone são da mesma pessoa".

Deque — as duas pontas em `O(1)`#

Um cluster é O(1) no fim e O(n) no começo: inserir na posição 0 empurra todo o resto. O deque é O(1) nas duas pontas.

adopt Arcane.Collections as C

d := C.deque([1, 2, 3])
C.push_left(d, 0)
out C.pop_left(d)     // 0
out C.pop(d)          // 3
out len(d)            // 2

A troca é clara: o deque ganha nas pontas e perde no acesso indexado. Use-o para fila (BFS, produtor-consumidor) e janela deslizante; para acesso aleatório, cluster.

Contador — contar sem laço aninhado#

Contar ocorrências percorrendo e comparando é O(n²). Com um vault de contagem é O(n), e o counter é isso pronto:

adopt Arcane.Collections as C

palavras := ["a", "b", "a", "c", "a"]
out C.counter(palavras)                  // {a: 3, b: 1, c: 1}
out C.most_common(palavras, 2)           // [[a, 3], [b, 1]]

most_common(n) usa heap por dentro: O(n log k), não O(n log n). As duas ideias desta página juntas.

Escolhendo em trinta segundos#

Por onde seguir#