PriorityQueue

const std = @import("std");
const expect = std.testing.expect;
const Order = std.math.Order;

fn ascU32(_: void, a: u32, b: u32) Order {
    return std.math.order(a, b);
}

test "min-heap: pop returns the smallest" {
    const gpa = std.testing.allocator;

    // The comparator is part of the type. Order.lt means "a pops first".
    var pq: std.PriorityQueue(u32, void, ascU32) = .empty;
    defer pq.deinit(gpa);

    try pq.push(gpa, 30);
    try pq.push(gpa, 10);
    try pq.push(gpa, 20);

    try expect(pq.peek().? == 10); // look without removing
    try expect(pq.pop().? == 10);
    try expect(pq.pop().? == 20);
    try expect(pq.pop().? == 30);
    try expect(pq.pop() == null);
}

const Job = struct {
    priority: u8,
    name: []const u8,
};

fn urgentFirst(_: void, a: Job, b: Job) Order {
    // Reverse the comparison to get a max-heap.
    return std.math.order(b.priority, a.priority);
}

test "structs with a priority field" {
    const gpa = std.testing.allocator;

    var jobs: std.PriorityQueue(Job, void, urgentFirst) = .empty;
    defer jobs.deinit(gpa);

    try jobs.pushSlice(gpa, &.{
        .{ .priority = 1, .name = "compact logs" },
        .{ .priority = 9, .name = "page the human" },
        .{ .priority = 5, .name = "rebuild index" },
    });

    try expect(std.mem.eql(u8, jobs.pop().?.name, "page the human"));
    try expect(std.mem.eql(u8, jobs.pop().?.name, "rebuild index"));
    try expect(jobs.count() == 1);
}

test "iteration order is not sorted order" {
    const gpa = std.testing.allocator;

    var pq: std.PriorityQueue(u32, void, ascU32) = .empty;
    defer pq.deinit(gpa);
    try pq.pushSlice(gpa, &.{ 5, 1, 4, 2, 3 });

    // The backing array is a heap, not a sorted list. Only pop is ordered.
    var sum: u32 = 0;
    var it = pq.iterator();
    while (it.next()) |v| sum += v;
    try expect(sum == 15);
    try expect(pq.pop().? == 1);
}

The comparator lives in the type

std.PriorityQueue(T, Context, compareFn) bakes the ordering into the type itself, the same shape std.sort uses. The function returns a std.math.Order: return .lt when the first argument should pop before the second. So the comparator reads like “which comes first,” and swapping its two arguments turns a min-heap into a max-heap.

The Context parameter is void when the comparison needs nothing external. Give it a real type to compare against runtime data, for example distances against a target you only know at run time; pass the value through initContext.

What it is good at

push and pop are O(log n); peek is O(1). You reach for it when you repeatedly need the current best element out of a changing set: a scheduler pulling the most urgent job, Dijkstra pulling the nearest node, a merge of sorted streams.

What it is not

The backing storage is a heap, not a sorted array. iterator walks that storage in heap order, which is not sorted order. Only pop gives you elements in priority sequence. If you need everything sorted once, an ArrayList plus std.sort is the better fit; the queue earns its keep when insertions and removals are interleaved.