# PriorityQueue

> A binary heap where the comparator is part of the type.

```zig
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);
}
```

*Runnable: compiled to WebAssembly and executed by CI against Zig master. (`03-standard-library.priority-queue`)*

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