跳转到内容

std.priority_queue

标准库Zig 0.17.0官方原文
源码std/priority_queue.zig

第 1 行

std.priority_queue.Allocator

别名

第 2 行

别名目标 std.mem.Allocator

std.priority_queue.assert

别名

第 3 行

别名目标 std.debug.assert

std.priority_queue.contextLessThan

函数

第 670 行

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

参数

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

std.priority_queue.expect

别名

第 6 行

别名目标 std.testing.expect

std.priority_queue.expectEqual

别名

第 7 行

别名目标 std.testing.expectEqual

std.priority_queue.expectError

别名

第 8 行

别名目标 std.testing.expectError

std.priority_queue.greaterThan

函数

第 287 行

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

参数

context: void
a: u32
b: u32

std.priority_queue.lessThan

函数

第 282 行

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

参数

context: void
a: u32
b: u32

std.priority_queue.MaxHeap

类型

第 292 行

std.priority_queue.MinHeap

类型

第 291 行

std.priority_queue.MinHeapWithContext

类型

第 674 行

std.priority_queue.Order

别名

第 4 行

别名目标 std.math.Order

std.priority_queue.PriorityQueue

类型函数

第 17 行

用于存储泛型数据的优先队列。用 init 初始化。 提供 compareFn:若第二个参数应在第三个 参数之前弹出,则返回 Order.lt; 优先级相同返回 Order.eq;若第三个 参数应先弹出,则返回 Order.gt。 例如,要使 pop 返回最小数,请提供: 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

参数

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

字段

items: []T
cap: usize
context: Context

std.priority_queue.PriorityQueue.allocatedSlice

函数

第 133 行

返回包含所有元素及额外容量的切片,额外容量的内存 内容为 undefined。

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

参数

self: *const Self

std.priority_queue.PriorityQueue.capacity

函数

第 127 行

返回在需要再次分配内存之前, 还能向队列添加的元素数量。

pub fn capacity(self: *const Self) usize

参数

self: *const Self

std.priority_queue.PriorityQueue.clearAndFree

函数

第 228 行

使所有元素指针失效。

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

参数

self: *Self
allocator: Allocator

std.priority_queue.PriorityQueue.clearRetainingCapacity

函数

第 223 行

移除 items 切片中的全部元素。

pub fn clearRetainingCapacity(self: *Self) void

参数

self: *Self

std.priority_queue.PriorityQueue.count

函数

第 121 行

返回优先队列中 剩余的元素数量。

pub fn count(self: *const Self) usize

参数

self: *const Self

std.priority_queue.PriorityQueue.deinit

函数

第 42 行

释放队列使用的内存。

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

参数

self: *Self
allocator: Allocator

std.priority_queue.PriorityQueue.empty

常量

第 26 行

不含任何元素的优先队列。

Self

std.priority_queue.PriorityQueue.ensureTotalCapacity

函数

第 177 行

确保队列至少能容纳 new_capacity 个元素。

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

参数

self: *Self
allocator: Allocator
new_capacity: usize

std.priority_queue.PriorityQueue.ensureTotalCapacityPrecise

函数

第 190 行

若当前容量小于 new_capacity,此函数会 修改数组,使其恰好能容纳 new_capacity 个元素。 若需要额外内存,则使元素指针失效。

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

参数

self: *Self
allocator: Allocator
new_capacity: usize

std.priority_queue.PriorityQueue.ensureUnusedCapacity

函数

第 200 行

确保队列至少还能额外容纳 additional_count 个项目。

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

参数

self: *Self
allocator: Allocator
additional_count: usize

std.priority_queue.PriorityQueue.fromOwnedSlice

函数

第 161 行

PriorityQueue 取得传入切片的所有权。该切片必须由 allocator 分配。 使用 deinit 释放。

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

参数

items: []T
context: Context

std.priority_queue.PriorityQueue.initContext

函数

第 33 行

使用上下文初始化并返回优先队列。

pub fn initContext(context: Context) Self

参数

context: Context

std.priority_queue.PriorityQueue.iterator

函数

第 273 行

返回遍历队列而不消耗元素的迭代器。 遍历顺序可能与优先级顺序不同。 堆发生修改后,迭代器失效。

pub fn iterator(self: *Self) Iterator

参数

self: *Self

std.priority_queue.PriorityQueue.Iterator

容器

第 254 行

字段

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

std.priority_queue.PriorityQueue.Iterator.next

函数

第 258 行

pub fn next(it: *Iterator) ?T

参数

it: *Iterator

std.priority_queue.PriorityQueue.Iterator.reset

函数

第 265 行

pub fn reset(it: *Iterator) void

参数

it: *Iterator

std.priority_queue.PriorityQueue.peek

函数

第 82 行

查看队列中优先级最高的元素。队列为空则返回 null。

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

参数

self: *const Self

std.priority_queue.PriorityQueue.pop

函数

第 88 行

从队列中移除并返回优先级最高的元素。 若为空,则返回 null。

pub fn pop(self: *Self) ?T

参数

self: *Self

std.priority_queue.PriorityQueue.popIndex

函数

第 95 行

移除并返回索引处的元素。索引顺序 与迭代器相同,不一定是优先级 顺序。

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

参数

self: *Self
index: usize

std.priority_queue.PriorityQueue.push

函数

第 48 行

插入新元素并维持优先级。

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

参数

self: *Self
allocator: Allocator
elem: T

std.priority_queue.PriorityQueue.pushSlice

函数

第 73 行

将 items 中每个元素加入队列。

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

参数

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

std.priority_queue.PriorityQueue.pushUnchecked

函数

第 53 行

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

参数

self: *Self
elem: T

std.priority_queue.PriorityQueue.Self

别名

第 19 行

别名目标 std.priority_queue.PriorityQueue

std.priority_queue.PriorityQueue.shrinkAndFree

函数

第 205 行

将已分配容量减至 new_capacity。

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

参数

self: *Self
allocator: Allocator
new_capacity: usize

std.priority_queue.PriorityQueue.siftDown

函数

第 138 行

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

参数

self: *Self
target_index: usize

std.priority_queue.PriorityQueue.siftUp

函数

第 59 行

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

参数

self: *Self
start_index: usize

std.priority_queue.PriorityQueue.update

函数

第 236 行

以新元素替换队列中的元素,并保持优先级。 若待更新元素不存在,则返回 error.ElementNotFound。

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

参数

self: *Self
elem: T
new_elem: T

std.priority_queue.std

别名

第 1 行

别名目标 std

std.priority_queue.testing

别名

第 5 行

别名目标 std.testing

源码

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;

/// 用于存储泛型数据的优先队列。用 `init` 初始化。
/// 提供 `compareFn`:若第二个参数应在第三个
/// 参数之前弹出,则返回 `Order.lt`;
/// 优先级相同返回 `Order.eq`;若第三个
/// 参数应先弹出,则返回 `Order.gt`。
/// 例如,要使 `pop` 返回最小数,请提供:
/// `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,

        /// 不含任何元素的优先队列。
        pub const empty: Self = .{
            .items = &.{},
            .cap = 0,
            .context = undefined,
        };

        /// 使用上下文初始化并返回优先队列。
        pub fn initContext(context: Context) Self {
            return Self{
                .items = &.{},
                .cap = 0,
                .context = context,
            };
        }

        /// 释放队列使用的内存。
        pub fn deinit(self: *Self, allocator: Allocator) void {
            allocator.free(self.allocatedSlice());
            self.* = undefined;
        }

        /// 插入新元素并维持优先级。
        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;
        }

        /// 将 `items` 中每个元素加入队列。
        pub fn pushSlice(self: *Self, allocator: Allocator, items: []const T) !void {
            try self.ensureUnusedCapacity(allocator, items.len);
            for (items) |e| {
                self.pushUnchecked(e);
            }
        }

        /// 查看队列中优先级最高的元素。队列为空则返回
        /// `null`。
        pub fn peek(self: *const Self) ?T {
            return if (self.items.len > 0) self.items[0] else null;
        }

        /// 从队列中移除并返回优先级最高的元素。
        /// 若为空,则返回 `null`。
        pub fn pop(self: *Self) ?T {
            return if (self.items.len > 0) self.popIndex(0) else null;
        }

        /// 移除并返回索引处的元素。索引顺序
        /// 与迭代器相同,不一定是优先级
        /// 顺序。
        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) {
                // 已移除最后一个元素,无需其他操作。
            } 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;
        }

        /// 返回优先队列中
        /// 剩余的元素数量。
        pub fn count(self: *const Self) usize {
            return self.items.len;
        }

        /// 返回在需要再次分配内存之前,
        /// 还能向队列添加的元素数量。
        pub fn capacity(self: *const Self) usize {
            return self.cap;
        }

        /// 返回包含所有元素及额外容量的切片,额外容量的内存
        /// 内容为 `undefined`。
        fn allocatedSlice(self: *const Self) []T {
            // `items.len` 是长度,不是容量。
            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 取得传入切片的所有权。该切片必须由 `allocator` 分配。
        /// 使用 `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;
        }

        /// 确保队列至少能容纳 `new_capacity` 个元素。
        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);
        }

        /// 若当前容量小于 `new_capacity`,此函数会
        /// 修改数组,使其恰好能容纳 `new_capacity` 个元素。
        /// 若需要额外内存,则使元素指针失效。
        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;
        }

        /// 确保队列至少还能额外容纳 `additional_count` 个项目。
        pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_count: usize) !void {
            return self.ensureTotalCapacity(allocator, self.items.len + additional_count);
        }

        /// 将已分配容量减至 `new_capacity`。
        pub fn shrinkAndFree(self: *Self, allocator: Allocator, new_capacity: usize) void {
            assert(new_capacity <= self.cap);

            // 不能缩小到当前队列大小以下,否则会破坏堆性质
            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 => { // 没有问题,此时容量仍正确。
                    return;
                },
            };

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

        /// 移除 items 切片中的全部元素。
        pub fn clearRetainingCapacity(self: *Self) void {
            self.items.len = 0;
        }

        /// 使所有元素指针失效。
        pub fn clearAndFree(self: *Self, allocator: Allocator) void {
            allocator.free(self.allocatedSlice());
            self.items.len = 0;
            self.cap = 0;
        }

        /// 以新元素替换队列中的元素,并保持优先级。
        /// 若待更新元素不存在,则返回 `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 => {}, // 各项优先级相同,因此无需操作
            }
        }

        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;
            }
        };

        /// 返回遍历队列而不消耗元素的迭代器。
        /// 遍历顺序可能与优先级顺序不同。
        /// 堆发生修改后,迭代器失效。
        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());
}