std.PriorityQueue — Fila de Prioridade
O std.PriorityQueue implementa uma fila de prioridade baseada em heap binário. Ele permite inserir elementos com prioridades arbitrárias e sempre extrair o elemento de maior (ou menor) prioridade em tempo O(log n). É fundamental para algoritmos como Dijkstra, A*, agendamento de tarefas e processamento de eventos em ordem de prioridade.
Visão Geral
const std = @import("std");
const PriorityQueue = std.PriorityQueue;
Tipo e Assinatura
pub fn PriorityQueue(comptime T: type, comptime Context: type, comptime compareFn: fn (Context, T, T) std.math.Order) type
A função de comparação determina a ordem: para um min-heap, retorne .lt quando a < b; para um max-heap, inverta a lógica.
Funções Principais
Criação e Destruição
// Cria uma fila vazia
pub fn init(allocator: Allocator, context: Context) Self
// Libera memória
pub fn deinit(self: *Self) void
Inserção e Extração
// Insere um elemento
pub fn add(self: *Self, elem: T) Allocator.Error!void
// Remove e retorna o elemento de maior prioridade
pub fn remove(self: *Self) T
// Retorna sem remover
pub fn peek(self: Self) ?T
// Número de elementos
pub fn count(self: Self) usize
Operações Adicionais
// Adiciona um slice inteiro de elementos
pub fn addSlice(self: *Self, items: []const T) Allocator.Error!void
// Atualiza um elemento (remove e re-insere)
pub fn update(self: *Self, old: T, new: T) !void
Exemplo 1: Agendador de Tarefas por Prioridade
const std = @import("std");
const Tarefa = struct {
nome: []const u8,
prioridade: u8, // menor = mais urgente
};
fn compararTarefas(context: void, a: Tarefa, b: Tarefa) std.math.Order {
_ = context;
return std.math.order(a.prioridade, b.prioridade);
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var fila = std.PriorityQueue(Tarefa, void, compararTarefas).init(allocator, {});
defer fila.deinit();
// Adiciona tarefas com diferentes prioridades
try fila.add(.{ .nome = "Enviar relatório", .prioridade = 3 });
try fila.add(.{ .nome = "Corrigir bug crítico", .prioridade = 1 });
try fila.add(.{ .nome = "Atualizar docs", .prioridade = 5 });
try fila.add(.{ .nome = "Deploy em produção", .prioridade = 2 });
try fila.add(.{ .nome = "Revisar PR", .prioridade = 4 });
const stdout = std.io.getStdOut().writer();
try stdout.writeAll("Tarefas em ordem de prioridade:\n");
// Extrai na ordem de prioridade (menor número = maior prioridade)
while (fila.count() > 0) {
const tarefa = fila.remove();
try stdout.print(" [{d}] {s}\n", .{ tarefa.prioridade, tarefa.nome });
}
}
Exemplo 2: Merge de K Listas Ordenadas
const std = @import("std");
const Elemento = struct {
valor: i32,
lista_idx: usize,
pos: usize,
};
fn compararElementos(context: void, a: Elemento, b: Elemento) std.math.Order {
_ = context;
return std.math.order(a.valor, b.valor);
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// K listas ordenadas
const listas = [_][]const i32{
&[_]i32{ 1, 4, 7, 10 },
&[_]i32{ 2, 5, 8, 11 },
&[_]i32{ 3, 6, 9, 12 },
};
var pq = std.PriorityQueue(Elemento, void, compararElementos).init(allocator, {});
defer pq.deinit();
// Insere o primeiro elemento de cada lista
for (listas, 0..) |lista, i| {
if (lista.len > 0) {
try pq.add(.{ .valor = lista[0], .lista_idx = i, .pos = 0 });
}
}
var resultado = std.ArrayList(i32).init(allocator);
defer resultado.deinit();
// Merge usando a fila de prioridade
while (pq.count() > 0) {
const menor = pq.remove();
try resultado.append(menor.valor);
// Insere o próximo elemento da mesma lista
const prox_pos = menor.pos + 1;
if (prox_pos < listas[menor.lista_idx].len) {
try pq.add(.{
.valor = listas[menor.lista_idx][prox_pos],
.lista_idx = menor.lista_idx,
.pos = prox_pos,
});
}
}
const stdout = std.io.getStdOut().writer();
try stdout.print("Resultado do merge: ", .{});
for (resultado.items) |v| {
try stdout.print("{d} ", .{v});
}
try stdout.print("\n", .{});
}
Exemplo 3: Simulação de Eventos
const std = @import("std");
const Evento = struct {
tempo: u64, // timestamp em ms
tipo: Tipo,
descricao: []const u8,
const Tipo = enum { timer, io, usuario };
};
fn compararEventos(context: void, a: Evento, b: Evento) std.math.Order {
_ = context;
return std.math.order(a.tempo, b.tempo);
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var eventos = std.PriorityQueue(Evento, void, compararEventos).init(allocator, {});
defer eventos.deinit();
// Agenda eventos em tempos diferentes
try eventos.add(.{ .tempo = 500, .tipo = .io, .descricao = "Dados recebidos" });
try eventos.add(.{ .tempo = 100, .tipo = .timer, .descricao = "Timeout de conexão" });
try eventos.add(.{ .tempo = 300, .tipo = .usuario, .descricao = "Clique do mouse" });
try eventos.add(.{ .tempo = 150, .tipo = .timer, .descricao = "Heartbeat" });
try eventos.add(.{ .tempo = 200, .tipo = .io, .descricao = "Resposta HTTP" });
const stdout = std.io.getStdOut().writer();
try stdout.writeAll("Processando eventos:\n");
while (eventos.count() > 0) {
const ev = eventos.remove();
try stdout.print(" t={d:>4}ms [{s:>7}] {s}\n", .{
ev.tempo,
@tagName(ev.tipo),
ev.descricao,
});
}
}
Padrões Comuns
Min-Heap vs Max-Heap
// Min-heap (menor primeiro — padrão)
fn minOrder(ctx: void, a: i32, b: i32) std.math.Order {
_ = ctx;
return std.math.order(a, b);
}
// Max-heap (maior primeiro)
fn maxOrder(ctx: void, a: i32, b: i32) std.math.Order {
_ = ctx;
return std.math.order(b, a); // invertido
}
Módulos Relacionados
- std.ArrayList — Array dinâmico
- std.sort — Algoritmos de ordenação
- std.math — Funções matemáticas e Order