zig-skills/references/std-priority-queue.md

std.PriorityQueue (Zig 0.16.0)

Primary release-note source: https://ziglang.org/download/0.16.0/release-notes.html

Zig 0.16 changed priority queues to align with unmanaged containers:

• The queue no longer stores an allocator.
• Empty queues can use .empty.
• init -> initContext when context is needed.
• add -> push.
• The old unchecked insertion helper has no public pushUnchecked replacement; reserve and use supported public operations.
• addSlice -> pushSlice.
• remove / removeOrNull -> pop.
• removeIndex -> popIndex.

All examples below use the Zig 0.16 unmanaged API.

A binary heap-based priority queue. Efficiently retrieves elements by priority order.

When to Use

• Need to repeatedly extract min or max element
• Task scheduling by priority
• Dijkstra's algorithm, A* pathfinding
• Event-driven simulation (process earliest event first)

Initialization

const std = @import("std");

// Min-heap comparator (smallest first)
fn lessThan(context: void, a: u32, b: u32) std.math.Order {
    _ = context;
    return std.math.order(a, b);
}

const PQ = std.PriorityQueue(u32, void, lessThan);

var queue = PQ.initContext({});
defer queue.deinit(allocator);

Max-Heap

fn greaterThan(context: void, a: u32, b: u32) std.math.Order {
    _ = context;
    return std.math.order(a, b).invert();
}

const MaxPQ = std.PriorityQueue(u32, void, greaterThan);

Basic Operations

// Add elements
try queue.push(allocator, 54);
try queue.push(allocator, 12);
try queue.push(allocator, 7);

// Add multiple
try queue.pushSlice(allocator, &[_]u32{ 1, 2, 3 });

// Peek at highest priority (doesn't remove)
if (queue.peek()) |top| {
    std.debug.print("top: {}\n", .{top});  // 7 for min-heap
}

// Remove highest priority
const maybe_top = queue.pop(); // ?T; null when empty

// Size
const n = queue.count();
const cap = queue.capacity();

From Existing Slice

// Take ownership of slice, heapify in place
var items = try allocator.dupe(u32, &[_]u32{ 5, 3, 8, 1, 2 });
var queue = PQ.fromOwnedSlice(items, {});
defer queue.deinit(allocator);
// Now queue is a valid heap

Update Priority

// Change priority of existing element
try queue.update(old_value, new_value);
// Selection uses comparator equality. If duplicates compare equal, which one
// is updated is not a stable identity guarantee. Errors if no equal value exists.

Remove by Index

// Remove element at specific position (not priority order)
const removed = queue.popIndex(index); // asserts index < count; heap index is not priority rank

Iteration (Non-Priority Order)

// Iterate without removing (order is NOT priority order!)
var it = queue.iterator();
while (it.next()) |elem| {
    // process elem
}
it.reset();  // restart iteration

Any queue mutation invalidates the iterator.

Capacity Management

try queue.ensureTotalCapacity(allocator, 100);
try queue.ensureUnusedCapacity(allocator, 10);
queue.shrinkAndFree(allocator, new_capacity);
queue.clearRetainingCapacity();
queue.clearAndFree(allocator);

Context-Based Comparator

For comparing by external data (e.g., indices into an array):

fn compareByScore(scores: []const u32, a: usize, b: usize) std.math.Order {
    return std.math.order(scores[a], scores[b]);
}

const IndexPQ = std.PriorityQueue(usize, []const u32, compareByScore);

const scores = [_]u32{ 50, 30, 80, 20 };
var queue = IndexPQ.initContext(scores[0..]);
defer queue.deinit(allocator);

try queue.push(allocator, 0);  // score 50
try queue.push(allocator, 1);  // score 30
try queue.push(allocator, 2);  // score 80
try queue.push(allocator, 3);  // score 20

// Removes index 3 (score 20 is smallest)
const best = queue.pop().?;  // 3

Complete Example: Task Scheduler

const std = @import("std");

const Task = struct {
    name: []const u8,
    priority: u32,  // lower = more urgent
};

fn taskCompare(_: void, a: Task, b: Task) std.math.Order {
    return std.math.order(a.priority, b.priority);
}

const TaskQueue = std.PriorityQueue(Task, void, taskCompare);

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();

    const allocator = gpa.allocator();
    var tasks = TaskQueue.initContext({});
    defer tasks.deinit(allocator);

    try tasks.push(allocator, .{ .name = "low priority", .priority = 100 });
    try tasks.push(allocator, .{ .name = "urgent", .priority = 1 });
    try tasks.push(allocator, .{ .name = "medium", .priority = 50 });

    while (tasks.pop()) |task| {
        std.debug.print("Processing: {s}\n", .{task.name});
    }
    // Output:
    // Processing: urgent
    // Processing: medium
    // Processing: low priority
}

Notes

• Heap property: parent has higher priority than children
• pop() is nullable and O(log n); peek() is nullable and O(1)
• Iterator order is NOT priority order (it's heap array order)
• Use pop() for extraction from a potentially empty queue