---
title: "Fila de Prioridade em Zig: Binary Heap Min-Heap"
url: "https://ziglang.com.br/artigos/zig-fila-prioridade-binary-heap/"
markdown_url: "https://ziglang.com.br/artigos/zig-fila-prioridade-binary-heap.MD"
description: "Implemente uma fila de prioridade em Zig com binary heap: push, pop, decrease-key, complexidade O(log n), heapify, testes e uso em Dijkstra e schedulers."
date: "2026-09-17"
author: ""
---

# Fila de Prioridade em Zig: Binary Heap Min-Heap

Implemente uma fila de prioridade em Zig com binary heap: push, pop, decrease-key, complexidade O(log n), heapify, testes e uso em Dijkstra e schedulers.


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](/algoritmos/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](/artigos/zig-fila-limitada-mutex-condition-backpressure/): 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

| Operação | Efeito | Custo |
|---|---|---:|
| `peek` | Lê a raiz sem remover | O(1) |
| `push` | Insere e faz sift-up | O(log n) |
| `pop` | Remove a raiz e faz sift-down | O(log n) |
| `len` | Quantidade de itens | O(1) |
| construir de um slice | Heapify bottom-up | O(n) |

Í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.

```zig
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`:

```zig
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:

```zig
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](/algoritmos/dijkstra/) 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

| Estrutura | push | pop min | Quando escolher |
|---|---:|---:|---|
| Binary heap | O(log n) | O(log n) | Default em sistemas e algoritmos |
| Array ordenado | O(n) | O(1) | n pequeno, poucas inserções |
| Árvore balanceada | O(log n) | O(log n) | Precisa também buscar/remover arbitrário |
| Bucket queue / dial | O(1) amortizado | O(1) amortizado | Prioridades inteiras em faixa pequena |
| FIFO limitada | O(1) | O(1) | Sem prioridade, só ordem de chegada |

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](/artigos/zig-lru-cache-hashmap-lista-duplamente-encadeada/). Tampouco use heap quando a política é estritamente FIFO com backpressure entre threads; nesse caso a [fila com Mutex e Condition](/artigos/zig-fila-limitada-mutex-condition-backpressure/) é 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:

```zig
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](/artigos/zig-fuzz-testing-fuzzer-nativo/) 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:

| Conteúdo de `T` | Risco | Mitigação |
|---|---|---|
| inteiros / structs simples | Baixo | copiar por valor |
| slices emprestadas | Use-after-free | garantir lifetime ou duplicar |
| ponteiros alocados | Vazamento no `pop` esquecido | documentar dono e liberar no consumidor |
| handles de SO | Destruição dupla | transferir ownership no `pop` |

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.