Fila de Prioridade em Zig: Binary Heap Min-Heap

Para implementar uma fila de prioridade em Zig, use um binary heap sobre um ArrayList. Em uma min-heap, o menor elemento fica na raiz; cada pai é menor ou igual aos filhos. push coloca o item no fim e sobe até restaurar a propriedade; pop remove a raiz, traz o último elemento para o topo e desce até o lugar certo. O resultado é peek em O(1) e inserção/remoção em O(log n).

Essa estrutura aparece em Dijkstra, schedulers, merge de streams ordenados, timers, A*, Huffman e qualquer pipeline que precise sempre processar “o próximo mais urgente”. Ela não substitui uma fila limitada FIFO: FIFO preserva ordem de chegada; a heap ordena por chave de prioridade.

Este guia mostra uma min-heap genérica, as invariantes que o código precisa preservar, decrease-key preguiçoso para grafos, critérios de escolha e testes que realmente comprovam a ordem.

Resposta rápida: o contrato da min-heap

Índices no array:

• pai de i: (i - 1) / 2
• filho esquerdo: 2 * i + 1
• filho direito: 2 * i + 2

A propriedade da min-heap exige: para todo i > 0, items[parent(i)] <= items[i] segundo o comparador. Se essa relação quebrar, pop deixa de devolver o extremo correto.

Por que não ordenar o ArrayList a cada inserção

Ordenar depois de cada push custa O(n log n) no total por inserção completa, ou O(n) se você inserir na posição correta com deslocamento. Em laços quentes — relaxamento de arestas, expiração de timers, seleção de tarefas — esse custo cresce depressa.

A binary heap aceita uma ordem parcial. Ela não mantém o array totalmente ordenado; só garante que a raiz é o extremo. Isso basta para o contrato da fila de prioridade e reduz o trabalho por atualização a uma altura da árvore, cerca de log2(n).

Use array ordenado apenas quando:

1. o conjunto é pequeno e estável;
2. você precisa iterar em ordem completa com frequência;
3. inserções são raras e leituras ordenadas dominam.

Fora esses casos, a heap é o default.

Implementação genérica em Zig

A versão abaixo recebe um comparador em comptime. Para min-heap numérica, passe std.sort.asc(T); para max-heap, std.sort.desc(T). Os itens são armazenados por valor.

const std = @import("std");

pub fn PriorityQueue(
    comptime T: type,
    comptime Context: type,
    comptime lessThan: fn (Context, T, T) bool,
) type {
    return struct {
        const Self = @This();

        items: std.ArrayList(T),
        context: Context,

        pub fn init(allocator: std.mem.Allocator, context: Context) Self {
            return .{
                .items = std.ArrayList(T).init(allocator),
                .context = context,
            };
        }

        pub fn deinit(self: *Self) void {
            self.items.deinit();
        }

        pub fn len(self: *const Self) usize {
            return self.items.items.len;
        }

        pub fn peek(self: *const Self) ?T {
            if (self.items.items.len == 0) return null;
            return self.items.items[0];
        }

        pub fn push(self: *Self, value: T) !void {
            try self.items.append(value);
            self.siftUp(self.items.items.len - 1);
        }

        pub fn pop(self: *Self) ?T {
            const items = self.items.items;
            if (items.len == 0) return null;

            const root = items[0];
            const last = self.items.pop();
            if (self.items.items.len == 0) return root;

            self.items.items[0] = last;
            self.siftDown(0);
            return root;
        }

        fn parent(i: usize) usize {
            return (i - 1) / 2;
        }

        fn left(i: usize) usize {
            return 2 * i + 1;
        }

        fn siftUp(self: *Self, start: usize) void {
            var i = start;
            const items = self.items.items;
            while (i > 0) {
                const p = parent(i);
                if (!lessThan(self.context, items[i], items[p])) break;
                const tmp = items[i];
                items[i] = items[p];
                items[p] = tmp;
                i = p;
            }
        }

        fn siftDown(self: *Self, start: usize) void {
            var i = start;
            const items = self.items.items;
            while (true) {
                var smallest = i;
                const l = left(i);
                const r = l + 1;

                if (l < items.len and lessThan(self.context, items[l], items[smallest])) {
                    smallest = l;
                }
                if (r < items.len and lessThan(self.context, items[r], items[smallest])) {
                    smallest = r;
                }
                if (smallest == i) break;

                const tmp = items[i];
                items[i] = items[smallest];
                items[smallest] = tmp;
                i = smallest;
            }
        }
    };
}

fn i32Less(_: void, a: i32, b: i32) bool {
    return a < b;
}

test "min-heap pop returns values in ascending order" {
    var pq = PriorityQueue(i32, void, i32Less).init(std.testing.allocator, {});
    defer pq.deinit();

    try pq.push(5);
    try pq.push(1);
    try pq.push(3);
    try pq.push(1);

    try std.testing.expectEqual(@as(i32, 1), pq.pop().?);
    try std.testing.expectEqual(@as(i32, 1), pq.pop().?);
    try std.testing.expectEqual(@as(i32, 3), pq.pop().?);
    try std.testing.expectEqual(@as(i32, 5), pq.pop().?);
    try std.testing.expect(pq.pop() == null);
}

Observações práticas:

1. ArrayList pode mudar de assinatura entre releases; adapte init/append/pop à versão fixada no projeto.
2. O comparador deve definir uma ordem fraca consistente. Se lessThan(a,b) e lessThan(b,a) puderem ser ambos verdadeiros, a heap corrompe a ordem.
3. Empates são permitidos. A heap não é estável: dois itens com a mesma prioridade podem sair em qualquer ordem relativa.
4. Ownership de ponteiros ou slices dentro de T continua sendo do chamador, salvo se a fila duplicar recursos explicitamente.

Sift-up e sift-down sem mistério

siftUp corrige um valor pequeno demais que acabou de entrar no fim:

1. compare com o pai;
2. se for menor, troque;
3. repita até a raiz ou até achar um pai menor ou igual.

siftDown corrige um valor grande demais colocado na raiz após pop:

1. compare com os dois filhos;
2. troque com o menor filho se ele for menor que o atual;
3. repita até uma folha ou até ambos os filhos serem maiores ou iguais.

Essas rotinas são o coração da estrutura. Bugs clássicos:

• usar <= no lugar errado e criar loop infinito em empates;
• calcular filho direito como 2 * i + 1 em vez de 2 * i + 2;
• esquecer de verificar limites antes de ler items[r];
• chamar siftDown em heap vazia depois de pop do último elemento.

Teste esses limites com heaps de tamanho 0, 1 e 2 antes de confiar em um grafo grande.

Construção em O(n): heapify

Se você já tem um slice completo e quer transformá-lo em heap, não faça n vezes push (O(n log n)). Percorra os nós internos de baixo para cima e aplique siftDown:

pub fn fromOwnedSlice(
    allocator: std.mem.Allocator,
    context: Context,
    values: []T,
) !Self {
    var self = Self{
        .items = std.ArrayList(T).fromOwnedSlice(allocator, values),
        .context = context,
    };
    if (self.items.items.len < 2) return self;

    var i = (self.items.items.len / 2) - 1;
    while (true) {
        self.siftDown(i);
        if (i == 0) break;
        i -= 1;
    }
    return self;
}

A análise clássica mostra que a soma das alturas dos subheaps é linear. Use heapify ao construir a fila a partir de um snapshot; use push quando os dados chegam online.

Decrease-key: estrito ou preguiçoso

Algoritmos como Dijkstra precisam “melhorar” a prioridade de um item já presente. Há duas abordagens.

Decrease-key estrito

Você mantém um mapa elemento -> índice na heap, atualiza a chave e chama siftUp. É O(log n) por melhora, mas o código fica frágil: toda troca em siftUp/siftDown precisa atualizar o mapa de índices.

Decrease-key preguiçoso

Você simplesmente faz push de uma nova entrada (nova_distancia, vertice) e, no pop, descarta entradas obsoletas:

const Node = struct {
    dist: u64,
    vertex: usize,
};

fn nodeLess(_: void, a: Node, b: Node) bool {
    return a.dist < b.dist;
}

// Esboço do laço principal
while (pq.pop()) |node| {
    if (node.dist != dist[node.vertex]) continue; // entrada velha
    // relaxar arestas; se melhorar, push de novo
}

Para grafos esparsos, a versão preguiçosa costuma ser a melhor engenharia em Zig: menos estado auxiliar, menos bugs de índice e comportamento fácil de explicar em code review. A heap pode crescer com entradas mortas, então acompanhe len e o número de pops ignorados.

O artigo de Dijkstra em Zig começa pela matriz O(V²) justamente para evitar acoplar o aprendizado do algoritmo a detalhes de heap. Quando o grafo crescer, esta fila é a peça que falta.

Comparando opções de prioridade

Não use binary heap para implementar um cache LRU: a recência muda a cada get, e a estrutura certa é mapa + lista, como no cache LRU em Zig. Tampouco use heap quando a política é estritamente FIFO com backpressure entre threads; nesse caso a fila com Mutex e Condition é o desenho adequado.

Casos de uso em produção

Scheduler de tarefas

Guarde next_deadline_ns e um identificador. O worker faz peek, dorme até o deadline se necessário, depois pop e executa. Para timers recorrentes, calcule o próximo disparo e faça push de novo.

Merge de k streams ordenados

Empurre a cabeça de cada stream com a chave de ordenação. Ao consumir um item, empurre o próximo da mesma origem. É a base de k-way merge e de vários compactadores.

Melhor esforço sob carga

Se a fila de trabalho crescer demais, descarte da raiz oposta (máxima idade, menor prioridade) ou pare de aceitar push. A heap ajuda a decidir o que preservar; o limite de memória ainda precisa ser explícito.

Grafos e pathfinding

Além de Dijkstra, A* usa a mesma min-heap com f = g + h. Mantenha o comparador simples e coloque desempate explícito se a estabilidade importar para reprodução de testes.

Testes que importam

Além da ordem crescente no pop, cubra:

test "peek does not remove root" {
    var pq = PriorityQueue(i32, void, i32Less).init(std.testing.allocator, {});
    defer pq.deinit();

    try pq.push(2);
    try pq.push(0);
    try std.testing.expectEqual(@as(i32, 0), pq.peek().?);
    try std.testing.expectEqual(@as(usize, 2), pq.len());
    try std.testing.expectEqual(@as(i32, 0), pq.pop().?);
}

test "random pushes match sorted model" {
    var pq = PriorityQueue(i32, void, i32Less).init(std.testing.allocator, {});
    defer pq.deinit();

    var model = std.ArrayList(i32).init(std.testing.allocator);
    defer model.deinit();

    var prng = std.Random.DefaultPrng.init(0x16f00d);
    const random = prng.random();

    var i: usize = 0;
    while (i < 200) : (i += 1) {
        const value: i32 = @intCast(random.intRangeAtMost(i32, -50, 50));
        try pq.push(value);
        try model.append(value);
    }

    std.mem.sort(i32, model.items, {}, comptime std.sort.asc(i32));

    for (model.items) |expected| {
        try std.testing.expectEqual(expected, pq.pop().?);
    }
    try std.testing.expect(pq.pop() == null);
}

Complete com:

• pop e peek em fila vazia;
• valores duplicados;
• heapify produzindo a mesma sequência de pop que n pushes;
• comparador por struct (dist, depois vertex) para provar desempate explícito;
• uso com std.testing.allocator para detectar vazamento no deinit.

Se o projeto já tiver fuzzing, gere sequências de push/pop e compare com um modelo lento. O guia de fuzz testing em Zig mostra como encaixar esse tipo de oráculo.

Ownership, cópia e concorrência

Como no restante do Zig, a fila não adivinha quem libera memória:

Para acesso concorrente, a binary heap clássica não é lock-free. Um mutex em torno de push/pop resolve o caso simples. Se produtores e consumidores forem muitos e o perfil mostrar contenção, considere sharding por worker, uma heap por thread com merge periódico, ou uma fila FIFO para despacho e outra estrutura para prioridade local.

Checklist de code review

• comparador é consistente e sem NaN “surpresa” em floats;
• push faz sift-up e pop faz sift-down;
• pop do último elemento não chama sift em heap vazia;
• índices de filhos e pai estão corretos;
• empates têm comportamento aceito pelo chamador;
• ownership de T está documentado;
• decrease-key preguiçoso ignora entradas obsoletas;
• testes cobrem vazio, duplicatas e modelo ordenado;
• API da stdlib usada está fixada por versão;
• a fila não foi escolhida onde FIFO ou LRU seriam corretos.

Conclusão

Uma fila de prioridade em Zig bem feita é quase sempre um binary heap sobre um array dinâmico: pouco código, invariantes claras e custo logarítmico nas operações que importam. Comece pela min-heap genérica, prove a ordem com um modelo ordenado e só então encaixe Dijkstra, timers ou schedulers.

Quando a API da stdlib oscilar antes do 1.0, preserve o contrato — push, peek, pop, len — atrás de um tipo seu. Estruturas de prioridade são infraestrutura: o valor está em previsibilidade e testes, não em micro-otimizações prematuras.