Skip to content
Standard libraryZig 0.17.1Official documentation
Sourcestd/priority_queue.zig

Source line 1

std.priority_queue.Allocator

alias

Source line 2

Alias of std.mem.Allocator

std.priority_queue.assert

alias

Source line 3

Alias of std.debug.assert

std.priority_queue.contextLessThan

function

Source line 670

fn contextLessThan(context: []const u32, a: usize, b: usize) Order

Parameters

context: []const u32
a: usize
b: usize

std.priority_queue.expect

alias

Source line 6

Alias of std.testing.expect

std.priority_queue.expectEqual

alias

Source line 7

Alias of std.testing.expectEqual

std.priority_queue.expectError

alias

Source line 8

Alias of std.testing.expectError

std.priority_queue.greaterThan

function

Source line 287

fn greaterThan(context: void, a: u32, b: u32) Order

Parameters

context: void
a: u32
b: u32

std.priority_queue.lessThan

function

Source line 282

fn lessThan(context: void, a: u32, b: u32) Order

Parameters

context: void
a: u32
b: u32

std.priority_queue.MaxHeap

type

Source line 292

std.priority_queue.MinHeap

type

Source line 291

std.priority_queue.MinHeapWithContext

type

Source line 674

std.priority_queue.Order

alias

Source line 4

Alias of std.math.Order

std.priority_queue.PriorityQueue

type-function

Source line 17

Priority queue for storing generic data. Initialize with init. Provide compareFn that returns Order.lt when its second argument should get popped before its third argument, Order.eq if the arguments are of equal priority, or Order.gt if the third argument should be popped first. For example, to make pop return the smallest number, provide fn lessThan(context: void, a: T, b: T) Order { _ = context; return std.math.order(a, b); }

pub fn PriorityQueue(comptime T: type, comptime Context: type, comptime compareFn: fn (context: Context, a: T, b: T) Order) type

Parameters

T: type
Context: type
compareFn: fn (context: Context, a: T, b: T) Order

Fields

items: []T
cap: usize
context: Context

std.priority_queue.PriorityQueue.allocatedSlice

function

Source line 133

Returns a slice of all the items plus the extra capacity, whose memory contents are undefined.

fn allocatedSlice(self: *const Self) []T

Parameters

self: *const Self

std.priority_queue.PriorityQueue.capacity

function

Source line 127

Return the number of elements that can be added to the queue before more memory is allocated.

pub fn capacity(self: *const Self) usize

Parameters

self: *const Self

std.priority_queue.PriorityQueue.clearAndFree

function

Source line 228

Invalidates all element pointers.

pub fn clearAndFree(self: *Self, allocator: Allocator) void

Parameters

self: *Self
allocator: Allocator

std.priority_queue.PriorityQueue.clearRetainingCapacity

function

Source line 223

Remove all elements from the items slice.

pub fn clearRetainingCapacity(self: *Self) void

Parameters

self: *Self

std.priority_queue.PriorityQueue.count

function

Source line 121

Return the number of elements remaining in the priority queue.

pub fn count(self: *const Self) usize

Parameters

self: *const Self

std.priority_queue.PriorityQueue.deinit

function

Source line 42

Free memory used by the queue.

pub fn deinit(self: *Self, allocator: Allocator) void

Parameters

self: *Self
allocator: Allocator

std.priority_queue.PriorityQueue.empty

constant

Source line 26

A priority queue containing no elements.

Self

std.priority_queue.PriorityQueue.ensureTotalCapacity

function

Source line 177

Ensure that the queue can fit at least new_capacity items.

pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_capacity: usize) !void

Parameters

self: *Self
allocator: Allocator
new_capacity: usize

std.priority_queue.PriorityQueue.ensureTotalCapacityPrecise

function

Source line 190

If the current capacity is less than new_capacity, this function will modify the array so that it can hold exactly new_capacity items. Invalidates element pointers if additional memory is needed.

pub fn ensureTotalCapacityPrecise(self: *Self, allocator: Allocator, new_capacity: usize) !void

Parameters

self: *Self
allocator: Allocator
new_capacity: usize

std.priority_queue.PriorityQueue.ensureUnusedCapacity

function

Source line 200

Ensure that the queue can fit at least additional_count more item.

pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_count: usize) !void

Parameters

self: *Self
allocator: Allocator
additional_count: usize

std.priority_queue.PriorityQueue.fromOwnedSlice

function

Source line 161

PriorityQueue takes ownership of the passed in slice. The slice must have been allocated with allocator. Deinitialize with deinit.

pub fn fromOwnedSlice(items: []T, context: Context) Self

Parameters

items: []T
context: Context

std.priority_queue.PriorityQueue.initContext

function

Source line 33

Initialize and return a priority queue with context.

pub fn initContext(context: Context) Self

Parameters

context: Context

std.priority_queue.PriorityQueue.iterator

function

Source line 273

Return an iterator that walks the queue without consuming it. The iteration order may differ from the priority order. Invalidated if the heap is modified.

pub fn iterator(self: *Self) Iterator

Parameters

self: *Self

std.priority_queue.PriorityQueue.Iterator

container

Source line 254

Fields

queue: *PriorityQueue(T, Context, compareFn)
count: usize

std.priority_queue.PriorityQueue.Iterator.next

function

Source line 258

pub fn next(it: *Iterator) ?T

Parameters

it: *Iterator

std.priority_queue.PriorityQueue.Iterator.reset

function

Source line 265

pub fn reset(it: *Iterator) void

Parameters

it: *Iterator

std.priority_queue.PriorityQueue.peek

function

Source line 82

Look at the highest priority element in the queue. Returns null if empty.

pub fn peek(self: *const Self) ?T

Parameters

self: *const Self

std.priority_queue.PriorityQueue.pop

function

Source line 88

Remove and return the highest priority element from the queue. Returns null if empty.

pub fn pop(self: *Self) ?T

Parameters

self: *Self

std.priority_queue.PriorityQueue.popIndex

function

Source line 95

Remove and return element at index. Indices are in the same order as iterator, which is not necessarily priority order.

pub fn popIndex(self: *Self, index: usize) T

Parameters

self: *Self
index: usize

std.priority_queue.PriorityQueue.push

function

Source line 48

Insert a new element, maintaining priority.

pub fn push(self: *Self, allocator: Allocator, elem: T) !void

Parameters

self: *Self
allocator: Allocator
elem: T

std.priority_queue.PriorityQueue.pushSlice

function

Source line 73

Add each element in items to the queue.

pub fn pushSlice(self: *Self, allocator: Allocator, items: []const T) !void

Parameters

self: *Self
allocator: Allocator
items: []const T

std.priority_queue.PriorityQueue.pushUnchecked

function

Source line 53

fn pushUnchecked(self: *Self, elem: T) void

Parameters

self: *Self
elem: T

std.priority_queue.PriorityQueue.Self

alias

Source line 19

Alias of std.priority_queue.PriorityQueue

std.priority_queue.PriorityQueue.shrinkAndFree

function

Source line 205

Reduce allocated capacity to new_capacity.

pub fn shrinkAndFree(self: *Self, allocator: Allocator, new_capacity: usize) void

Parameters

self: *Self
allocator: Allocator
new_capacity: usize

std.priority_queue.PriorityQueue.siftDown

function

Source line 138

fn siftDown(self: *Self, target_index: usize) void

Parameters

self: *Self
target_index: usize

std.priority_queue.PriorityQueue.siftUp

function

Source line 59

fn siftUp(self: *Self, start_index: usize) void

Parameters

self: *Self
start_index: usize

std.priority_queue.PriorityQueue.update

function

Source line 236

Replace an element in the queue with a new element, maintaining priority. If the element being updated doesn't exist, return error.ElementNotFound.

pub fn update(self: *Self, elem: T, new_elem: T) !void

Parameters

self: *Self
elem: T
new_elem: T

std.priority_queue.std

alias

Source line 1

Alias of std

std.priority_queue.testing

alias

Source line 5

Alias of std.testing

Source code

std/priority_queue.zig

const std = @import("std.zig");
const Allocator = std.mem.Allocator;
const assert = std.debug.assert;
const Order = std.math.Order;
const testing = std.testing;
const expect = testing.expect;
const expectEqual = testing.expectEqual;
const expectError = testing.expectError;

/// Priority queue for storing generic data. Initialize with `init`.
/// Provide `compareFn` that returns `Order.lt` when its second
/// argument should get popped before its third argument,
/// `Order.eq` if the arguments are of equal priority, or `Order.gt`
/// if the third argument should be popped first.
/// For example, to make `pop` return the smallest number, provide
/// `fn lessThan(context: void, a: T, b: T) Order { _ = context; return std.math.order(a, b); }`
pub fn PriorityQueue(comptime T: type, comptime Context: type, comptime compareFn: fn (context: Context, a: T, b: T) Order) type {
    return struct {
        const Self = @This();

        items: []T,
        cap: usize,
        context: Context,

        /// A priority queue containing no elements.
        pub const empty: Self = .{
            .items = &.{},
            .cap = 0,
            .context = undefined,
        };

        /// Initialize and return a priority queue with context.
        pub fn initContext(context: Context) Self {
            return Self{
                .items = &.{},
                .cap = 0,
                .context = context,
            };
        }

        /// Free memory used by the queue.
        pub fn deinit(self: *Self, allocator: Allocator) void {
            allocator.free(self.allocatedSlice());
            self.* = undefined;
        }

        /// Insert a new element, maintaining priority.
        pub fn push(self: *Self, allocator: Allocator, elem: T) !void {
            try self.ensureUnusedCapacity(allocator, 1);
            pushUnchecked(self, elem);
        }

        fn pushUnchecked(self: *Self, elem: T) void {
            self.items.len += 1;
            self.items[self.items.len - 1] = elem;
            siftUp(self, self.items.len - 1);
        }

        fn siftUp(self: *Self, start_index: usize) void {
            const child = self.items[start_index];
            var child_index = start_index;
            while (child_index > 0) {
                const parent_index = ((child_index - 1) >> 1);
                const parent = self.items[parent_index];
                if (compareFn(self.context, child, parent) != .lt) break;
                self.items[child_index] = parent;
                child_index = parent_index;
            }
            self.items[child_index] = child;
        }

        /// Add each element in `items` to the queue.
        pub fn pushSlice(self: *Self, allocator: Allocator, items: []const T) !void {
            try self.ensureUnusedCapacity(allocator, items.len);
            for (items) |e| {
                self.pushUnchecked(e);
            }
        }

        /// Look at the highest priority element in the queue. Returns
        /// `null` if empty.
        pub fn peek(self: *const Self) ?T {
            return if (self.items.len > 0) self.items[0] else null;
        }

        /// Remove and return the highest priority element from the queue.
        /// Returns `null` if empty.
        pub fn pop(self: *Self) ?T {
            return if (self.items.len > 0) self.popIndex(0) else null;
        }

        /// Remove and return element at index. Indices are in the
        /// same order as iterator, which is not necessarily priority
        /// order.
        pub fn popIndex(self: *Self, index: usize) T {
            assert(self.items.len > index);
            const last = self.items[self.items.len - 1];
            const item = self.items[index];
            self.items[index] = last;
            self.items.len -= 1;

            if (index == self.items.len) {
                // Last element removed, nothing more to do.
            } else if (index == 0) {
                siftDown(self, index);
            } else {
                const parent_index = ((index - 1) >> 1);
                const parent = self.items[parent_index];
                if (compareFn(self.context, last, parent) == .gt) {
                    siftDown(self, index);
                } else {
                    siftUp(self, index);
                }
            }

            return item;
        }

        /// Return the number of elements remaining in the priority
        /// queue.
        pub fn count(self: *const Self) usize {
            return self.items.len;
        }

        /// Return the number of elements that can be added to the
        /// queue before more memory is allocated.
        pub fn capacity(self: *const Self) usize {
            return self.cap;
        }

        /// Returns a slice of all the items plus the extra capacity, whose memory
        /// contents are `undefined`.
        fn allocatedSlice(self: *const Self) []T {
            // `items.len` is the length, not the capacity.
            return self.items.ptr[0..self.cap];
        }

        fn siftDown(self: *Self, target_index: usize) void {
            const target_element = self.items[target_index];
            var index = target_index;
            while (true) {
                var lesser_child_i = (std.math.mul(usize, index, 2) catch break) | 1;
                if (!(lesser_child_i < self.items.len)) break;

                const next_child_i = lesser_child_i + 1;
                if (next_child_i < self.items.len and compareFn(self.context, self.items[next_child_i], self.items[lesser_child_i]) == .lt) {
                    lesser_child_i = next_child_i;
                }

                if (compareFn(self.context, target_element, self.items[lesser_child_i]) == .lt) break;

                self.items[index] = self.items[lesser_child_i];
                index = lesser_child_i;
            }
            self.items[index] = target_element;
        }

        /// PriorityQueue takes ownership of the passed in slice. The slice must have been
        /// allocated with `allocator`.
        /// Deinitialize with `deinit`.
        pub fn fromOwnedSlice(items: []T, context: Context) Self {
            var self = Self{
                .items = items,
                .cap = items.len,
                .context = context,
            };

            var i = self.items.len >> 1;
            while (i > 0) {
                i -= 1;
                self.siftDown(i);
            }
            return self;
        }

        /// Ensure that the queue can fit at least `new_capacity` items.
        pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_capacity: usize) !void {
            var better_capacity = self.cap;
            if (better_capacity >= new_capacity) return;
            while (true) {
                better_capacity += better_capacity / 2 + 8;
                if (better_capacity >= new_capacity) break;
            }
            try self.ensureTotalCapacityPrecise(allocator, better_capacity);
        }

        /// If the current capacity is less than `new_capacity`, this function will
        /// modify the array so that it can hold exactly `new_capacity` items.
        /// Invalidates element pointers if additional memory is needed.
        pub fn ensureTotalCapacityPrecise(self: *Self, allocator: Allocator, new_capacity: usize) !void {
            if (self.capacity() >= new_capacity) return;

            const old_memory = self.allocatedSlice();
            const new_memory = try allocator.realloc(old_memory, new_capacity);
            self.items.ptr = new_memory.ptr;
            self.cap = new_memory.len;
        }

        /// Ensure that the queue can fit at least `additional_count` **more** item.
        pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_count: usize) !void {
            return self.ensureTotalCapacity(allocator, self.items.len + additional_count);
        }

        /// Reduce allocated capacity to `new_capacity`.
        pub fn shrinkAndFree(self: *Self, allocator: Allocator, new_capacity: usize) void {
            assert(new_capacity <= self.cap);

            // Cannot shrink to smaller than the current queue size without invalidating the heap property
            assert(new_capacity >= self.items.len);

            const old_memory = self.allocatedSlice();
            const new_memory = allocator.realloc(old_memory, new_capacity) catch |e| switch (e) {
                error.OutOfMemory => { // no problem, capacity is still correct then.
                    return;
                },
            };

            self.items.ptr = new_memory.ptr;
            self.cap = new_memory.len;
        }

        /// Remove all elements from the items slice.
        pub fn clearRetainingCapacity(self: *Self) void {
            self.items.len = 0;
        }

        /// Invalidates all element pointers.
        pub fn clearAndFree(self: *Self, allocator: Allocator) void {
            allocator.free(self.allocatedSlice());
            self.items.len = 0;
            self.cap = 0;
        }

        /// Replace an element in the queue with a new element, maintaining priority.
        /// If the element being updated doesn't exist, return `error.ElementNotFound`.
        pub fn update(self: *Self, elem: T, new_elem: T) !void {
            const update_index = blk: {
                var idx: usize = 0;
                while (idx < self.items.len) : (idx += 1) {
                    const item = self.items[idx];
                    if (compareFn(self.context, item, elem) == .eq) break :blk idx;
                }
                return error.ElementNotFound;
            };
            const old_elem: T = self.items[update_index];
            self.items[update_index] = new_elem;
            switch (compareFn(self.context, new_elem, old_elem)) {
                .lt => siftUp(self, update_index),
                .gt => siftDown(self, update_index),
                .eq => {}, // Nothing to do as the items have equal priority
            }
        }

        pub const Iterator = struct {
            queue: *PriorityQueue(T, Context, compareFn),
            count: usize,

            pub fn next(it: *Iterator) ?T {
                if (it.count >= it.queue.items.len) return null;
                const out = it.count;
                it.count += 1;
                return it.queue.items[out];
            }

            pub fn reset(it: *Iterator) void {
                it.count = 0;
            }
        };

        /// Return an iterator that walks the queue without consuming
        /// it. The iteration order may differ from the priority order.
        /// Invalidated if the heap is modified.
        pub fn iterator(self: *Self) Iterator {
            return Iterator{
                .queue = self,
                .count = 0,
            };
        }
    };
}

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

fn greaterThan(context: void, a: u32, b: u32) Order {
    return lessThan(context, a, b).invert();
}

const MinHeap = PriorityQueue(u32, void, lessThan);
const MaxHeap = PriorityQueue(u32, void, greaterThan);

test "add and remove min heap" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    try queue.push(gpa, 54);
    try queue.push(gpa, 12);
    try queue.push(gpa, 7);
    try queue.push(gpa, 23);
    try queue.push(gpa, 25);
    try queue.push(gpa, 13);
    try expectEqual(@as(u32, 7), queue.pop());
    try expectEqual(@as(u32, 12), queue.pop());
    try expectEqual(@as(u32, 13), queue.pop());
    try expectEqual(@as(u32, 23), queue.pop());
    try expectEqual(@as(u32, 25), queue.pop());
    try expectEqual(@as(u32, 54), queue.pop());
}

test "add and remove same min heap" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    try queue.push(gpa, 1);
    try queue.push(gpa, 1);
    try queue.push(gpa, 2);
    try queue.push(gpa, 2);
    try queue.push(gpa, 1);
    try queue.push(gpa, 1);
    try expectEqual(@as(u32, 1), queue.pop());
    try expectEqual(@as(u32, 1), queue.pop());
    try expectEqual(@as(u32, 1), queue.pop());
    try expectEqual(@as(u32, 1), queue.pop());
    try expectEqual(@as(u32, 2), queue.pop());
    try expectEqual(@as(u32, 2), queue.pop());
}

test "removeOrNull on empty" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    try expect(queue.pop() == null);
}

test "edge case 3 elements" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    try queue.push(gpa, 9);
    try queue.push(gpa, 3);
    try queue.push(gpa, 2);
    try expectEqual(@as(u32, 2), queue.pop());
    try expectEqual(@as(u32, 3), queue.pop());
    try expectEqual(@as(u32, 9), queue.pop());
}

test "peek" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    try expect(queue.peek() == null);
    try queue.push(gpa, 9);
    try queue.push(gpa, 3);
    try queue.push(gpa, 2);
    try expectEqual(@as(u32, 2), queue.peek().?);
    try expectEqual(@as(u32, 2), queue.peek().?);
}

test "sift up with odd indices" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    const items = [_]u32{ 15, 7, 21, 14, 13, 22, 12, 6, 7, 25, 5, 24, 11, 16, 15, 24, 2, 1 };
    for (items) |e| {
        try queue.push(gpa, e);
    }

    const sorted_items = [_]u32{ 1, 2, 5, 6, 7, 7, 11, 12, 13, 14, 15, 15, 16, 21, 22, 24, 24, 25 };
    for (sorted_items) |e| {
        try expectEqual(e, queue.pop());
    }
}

test "addSlice" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    const items = [_]u32{ 15, 7, 21, 14, 13, 22, 12, 6, 7, 25, 5, 24, 11, 16, 15, 24, 2, 1 };
    try queue.pushSlice(gpa, items[0..]);

    const sorted_items = [_]u32{ 1, 2, 5, 6, 7, 7, 11, 12, 13, 14, 15, 15, 16, 21, 22, 24, 24, 25 };
    for (sorted_items) |e| {
        try expectEqual(e, queue.pop());
    }
}

test "fromOwnedSlice trivial case 0" {
    const gpa = testing.allocator;

    const items = [0]u32{};
    const queue_items = try gpa.dupe(u32, &items);

    var queue: MinHeap = .fromOwnedSlice(queue_items[0..], {});
    defer queue.deinit(gpa);

    try expectEqual(@as(usize, 0), queue.count());
    try expect(queue.pop() == null);
}

test "fromOwnedSlice trivial case 1" {
    const gpa = testing.allocator;

    const items = [1]u32{1};
    const queue_items = try gpa.dupe(u32, &items);

    var queue: MinHeap = .fromOwnedSlice(queue_items[0..], {});
    defer queue.deinit(gpa);

    try expectEqual(@as(usize, 1), queue.count());
    try expectEqual(items[0], queue.pop());
    try expect(queue.pop() == null);
}

test "fromOwnedSlice" {
    const gpa = testing.allocator;

    const items = [_]u32{ 15, 7, 21, 14, 13, 22, 12, 6, 7, 25, 5, 24, 11, 16, 15, 24, 2, 1 };
    const heap_items = try gpa.dupe(u32, items[0..]);

    var queue: MinHeap = .fromOwnedSlice(heap_items[0..], {});
    defer queue.deinit(gpa);

    const sorted_items = [_]u32{ 1, 2, 5, 6, 7, 7, 11, 12, 13, 14, 15, 15, 16, 21, 22, 24, 24, 25 };
    for (sorted_items) |e| {
        try expectEqual(e, queue.pop());
    }
}

test "add and remove max heap" {
    const gpa = testing.allocator;

    var queue: MaxHeap = .empty;
    defer queue.deinit(gpa);

    try queue.push(gpa, 54);
    try queue.push(gpa, 12);
    try queue.push(gpa, 7);
    try queue.push(gpa, 23);
    try queue.push(gpa, 25);
    try queue.push(gpa, 13);
    try expectEqual(@as(u32, 54), queue.pop());
    try expectEqual(@as(u32, 25), queue.pop());
    try expectEqual(@as(u32, 23), queue.pop());
    try expectEqual(@as(u32, 13), queue.pop());
    try expectEqual(@as(u32, 12), queue.pop());
    try expectEqual(@as(u32, 7), queue.pop());
}

test "add and remove same max heap" {
    const gpa = testing.allocator;

    var queue: MaxHeap = .empty;
    defer queue.deinit(gpa);

    try queue.push(gpa, 1);
    try queue.push(gpa, 1);
    try queue.push(gpa, 2);
    try queue.push(gpa, 2);
    try queue.push(gpa, 1);
    try queue.push(gpa, 1);
    try expectEqual(@as(u32, 2), queue.pop());
    try expectEqual(@as(u32, 2), queue.pop());
    try expectEqual(@as(u32, 1), queue.pop());
    try expectEqual(@as(u32, 1), queue.pop());
    try expectEqual(@as(u32, 1), queue.pop());
    try expectEqual(@as(u32, 1), queue.pop());
}

test "iterator" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    var map = std.AutoHashMap(u32, void).init(testing.allocator);
    defer {
        queue.deinit(gpa);
        map.deinit();
    }

    const items = [_]u32{ 54, 12, 7, 23, 25, 13 };
    for (items) |e| {
        _ = try queue.push(gpa, e);
        try map.put(e, {});
    }

    var it = queue.iterator();
    while (it.next()) |e| {
        _ = map.remove(e);
    }

    try expectEqual(@as(usize, 0), map.count());
}

test "remove at index" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    const items = [_]u32{ 2, 1, 8, 9, 3, 4, 5 };
    for (items) |e| {
        _ = try queue.push(gpa, e);
    }

    var it = queue.iterator();
    var idx: usize = 0;
    const two_idx = while (it.next()) |elem| {
        if (elem == 2)
            break idx;
        idx += 1;
    } else unreachable;
    const sorted_items = [_]u32{ 1, 3, 4, 5, 8, 9 };
    try expectEqual(queue.popIndex(two_idx), 2);

    var i: usize = 0;
    while (queue.pop()) |n| : (i += 1) {
        try expectEqual(n, sorted_items[i]);
    }
    try expectEqual(queue.pop(), null);
}

test "iterator while empty" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    var it = queue.iterator();

    try expectEqual(it.next(), null);
}

test "shrinkAndFree" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    try queue.ensureTotalCapacity(gpa, 4);
    try expect(queue.capacity() >= 4);

    try queue.push(gpa, 1);
    try queue.push(gpa, 2);
    try queue.push(gpa, 3);
    try expect(queue.capacity() >= 4);
    try expectEqual(@as(usize, 3), queue.count());

    queue.shrinkAndFree(gpa, 3);
    try expectEqual(@as(usize, 3), queue.capacity());
    try expectEqual(@as(usize, 3), queue.count());

    try expectEqual(@as(u32, 1), queue.pop());
    try expectEqual(@as(u32, 2), queue.pop());
    try expectEqual(@as(u32, 3), queue.pop());
    try expect(queue.pop() == null);
}

test "update min heap" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    try queue.push(gpa, 55);
    try queue.push(gpa, 44);
    try queue.push(gpa, 11);
    try queue.update(55, 5);
    try queue.update(44, 4);
    try queue.update(11, 1);
    try expectEqual(@as(u32, 1), queue.pop());
    try expectEqual(@as(u32, 4), queue.pop());
    try expectEqual(@as(u32, 5), queue.pop());
}

test "update same min heap" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    try queue.push(gpa, 1);
    try queue.push(gpa, 1);
    try queue.push(gpa, 2);
    try queue.push(gpa, 2);
    try queue.update(1, 5);
    try queue.update(2, 4);
    try expectEqual(@as(u32, 1), queue.pop());
    try expectEqual(@as(u32, 2), queue.pop());
    try expectEqual(@as(u32, 4), queue.pop());
    try expectEqual(@as(u32, 5), queue.pop());
}

test "update max heap" {
    const gpa = testing.allocator;

    var queue: MaxHeap = .empty;
    defer queue.deinit(gpa);

    try queue.push(gpa, 55);
    try queue.push(gpa, 44);
    try queue.push(gpa, 11);
    try queue.update(55, 5);
    try queue.update(44, 1);
    try queue.update(11, 4);
    try expectEqual(@as(u32, 5), queue.pop());
    try expectEqual(@as(u32, 4), queue.pop());
    try expectEqual(@as(u32, 1), queue.pop());
}

test "update same max heap" {
    const gpa = testing.allocator;

    var queue: MaxHeap = .empty;
    defer queue.deinit(gpa);

    try queue.push(gpa, 1);
    try queue.push(gpa, 1);
    try queue.push(gpa, 2);
    try queue.push(gpa, 2);
    try queue.update(1, 5);
    try queue.update(2, 4);
    try expectEqual(@as(u32, 5), queue.pop());
    try expectEqual(@as(u32, 4), queue.pop());
    try expectEqual(@as(u32, 2), queue.pop());
    try expectEqual(@as(u32, 1), queue.pop());
}

test "update after remove" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    try queue.push(gpa, 1);
    try expectEqual(@as(u32, 1), queue.pop());
    try expectError(error.ElementNotFound, queue.update(1, 1));
}

test "siftUp in remove" {
    const gpa = testing.allocator;

    var queue: MinHeap = .empty;
    defer queue.deinit(gpa);

    try queue.pushSlice(gpa, &.{ 0, 1, 100, 2, 3, 101, 102, 4, 5, 6, 7, 103, 104, 105, 106, 8 });

    _ = queue.popIndex(std.mem.findScalar(u32, queue.items[0..queue.count()], 102).?);

    const sorted_items = [_]u32{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 100, 101, 103, 104, 105, 106 };
    for (sorted_items) |e| {
        try expectEqual(e, queue.pop());
    }
}

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

const MinHeapWithContext = PriorityQueue(usize, []const u32, contextLessThan);

test "add and remove min heap with context comparator" {
    const gpa = testing.allocator;

    const context = [_]u32{ 5, 3, 4, 2, 2, 8, 0 };

    var queue: MinHeapWithContext = .initContext(context[0..]);
    defer queue.deinit(gpa);

    try queue.push(gpa, 0);
    try queue.push(gpa, 1);
    try queue.push(gpa, 2);
    try queue.push(gpa, 3);
    try queue.push(gpa, 4);
    try queue.push(gpa, 5);
    try queue.push(gpa, 6);
    try expectEqual(@as(usize, 6), queue.pop());
    try expectEqual(@as(usize, 4), queue.pop());
    try expectEqual(@as(usize, 3), queue.pop());
    try expectEqual(@as(usize, 1), queue.pop());
    try expectEqual(@as(usize, 2), queue.pop());
    try expectEqual(@as(usize, 0), queue.pop());
    try expectEqual(@as(usize, 5), queue.pop());
}