Skip to content

std.priority_dequeue

Standard libraryZig 0.17.0Official documentation
Sourcestd/priority_dequeue.zig

Source line 1

std.priority_dequeue.all_cmps_unique

variable

Source line 1065

std.priority_dequeue.Allocator

alias

Source line 2

Alias of std.mem.Allocator

std.priority_dequeue.assert

alias

Source line 3

Alias of std.debug.assert

std.priority_dequeue.contextLessThanComparison

function

Source line 1035

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

Parameters

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

std.priority_dequeue.expect

alias

Source line 6

Alias of std.testing.expect

std.priority_dequeue.expectEqual

alias

Source line 7

Alias of std.testing.expectEqual

std.priority_dequeue.expectError

alias

Source line 8

Alias of std.testing.expectError

std.priority_dequeue.fuzzTestMax

function

Source line 964

fn fuzzTestMax(rng: std.Random, queue_size: usize) !void

Parameters

rng: std.Random
queue_size: usize

std.priority_dequeue.fuzzTestMin

function

Source line 934

fn fuzzTestMin(rng: std.Random, comptime queue_size: usize) !void

Parameters

rng: std.Random
queue_size: usize

std.priority_dequeue.fuzzTestMinMax

function

Source line 994

fn fuzzTestMinMax(rng: std.Random, queue_size: usize) !void

Parameters

rng: std.Random
queue_size: usize

std.priority_dequeue.generateRandomSlice

function

Source line 1022

fn generateRandomSlice(allocator: std.mem.Allocator, rng: std.Random, size: usize) ![]u32

Parameters

allocator: std.mem.Allocator
rng: std.Random
size: usize

std.priority_dequeue.lessThanComparison

function

Source line 455

If a min heap is constructed from slice {5, 8, 2, 9, 7, 1, 4, 4} using this method, then the elements will be in order: {1, 2, 4, 4, 5, 7, 8, 9}

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

Parameters

context: void
a: u32
b: u32

std.priority_dequeue.MinHeap

type

Source line 461

Elements with lower priority will be removed first

std.priority_dequeue.MinHeapWithContext

type

Source line 1039

std.priority_dequeue.order

function

Source line 491

fn order(context: void, a: S, b: S) Order

Parameters

context: void
a: S
b: S

std.priority_dequeue.Order

alias

Source line 4

Alias of std.math.Order

std.priority_dequeue.PriorityDequeue

type-function

Source line 18

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

pub fn PriorityDequeue(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
len: usize
context: Context

std.priority_dequeue.PriorityDequeue.bestDescendent

function

Source line 286

fn bestDescendent(self: *const Self, first_child_index: usize, first_grandchild_index: usize, target_order: Order) ItemAndIndex

Parameters

self: *const Self
first_child_index: usize
first_grandchild_index: usize
target_order: Order

std.priority_dequeue.PriorityDequeue.bestItem

function

Source line 272

fn bestItem(self: *const Self, item1: ItemAndIndex, item2: ItemAndIndex, target_order: Order) ItemAndIndex

Parameters

self: *const Self
item1: ItemAndIndex
item2: ItemAndIndex
target_order: Order

std.priority_dequeue.PriorityDequeue.bestItemAtIndices

function

Source line 280

fn bestItemAtIndices(self: *const Self, index1: usize, index2: usize, target_order: Order) ItemAndIndex

Parameters

self: *const Self
index1: usize
index2: usize
target_order: Order

std.priority_dequeue.PriorityDequeue.capacity

function

Source line 324

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

pub fn capacity(self: *const Self) usize

Parameters

self: *const Self

std.priority_dequeue.PriorityDequeue.count

function

Source line 318

Return the number of elements remaining in the dequeue

pub fn count(self: *const Self) usize

Parameters

self: *const Self

std.priority_dequeue.PriorityDequeue.deinit

function

Source line 43

Free memory used by the dequeue.

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

Parameters

self: *Self
allocator: Allocator

std.priority_dequeue.PriorityDequeue.doSiftDown

function

Source line 193

fn doSiftDown(self: *Self, start_index: usize, target_order: Order) void

Parameters

self: *Self
start_index: usize
target_order: Order

std.priority_dequeue.PriorityDequeue.doSiftUp

function

Source line 121

fn doSiftUp(self: *Self, start_index: usize, target_order: Order) void

Parameters

self: *Self
start_index: usize
target_order: Order

std.priority_dequeue.PriorityDequeue.dump

function

Source line 418

fn dump(self: *Self) void

Parameters

self: *Self

std.priority_dequeue.PriorityDequeue.empty

constant

Source line 27

A priority dequeue containing no elements.

Self

std.priority_dequeue.PriorityDequeue.ensureTotalCapacity

function

Source line 349

Ensure that the dequeue 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_dequeue.PriorityDequeue.ensureUnusedCapacity

function

Source line 360

Ensure that the dequeue can fit at least additional_count more items.

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

Parameters

self: *Self
allocator: Allocator
additional_count: usize

std.priority_dequeue.PriorityDequeue.firstChildIndex

function

Source line 443

fn firstChildIndex(index: usize) usize

Parameters

index: usize

std.priority_dequeue.PriorityDequeue.firstGrandchildIndex

function

Source line 447

fn firstGrandchildIndex(index: usize) usize

Parameters

index: usize

std.priority_dequeue.PriorityDequeue.fromOwnedSlice

function

Source line 330

Dequeue takes ownership of the passed in slice. The slice must be de-initialize with deinit.

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

Parameters

items: []T
context: Context

std.priority_dequeue.PriorityDequeue.getItem

function

Source line 265

fn getItem(self: *const Self, index: usize) ItemAndIndex

Parameters

self: *const Self
index: usize

std.priority_dequeue.PriorityDequeue.getStartForSiftUp

function

Source line 90

fn getStartForSiftUp(self: *const Self, child: T, index: usize) StartIndexAndLayer

Parameters

self: *const Self
child: T
index: usize

std.priority_dequeue.PriorityDequeue.grandparentIndex

function

Source line 439

fn grandparentIndex(index: usize) usize

Parameters

index: usize

std.priority_dequeue.PriorityDequeue.initContext

function

Source line 34

Initialize and return a new priority dequeue with context.

pub fn initContext(context: Context) Self

Parameters

context: Context

std.priority_dequeue.PriorityDequeue.isMinLayer

function

Source line 73

fn isMinLayer(index: usize) bool

Parameters

index: usize

std.priority_dequeue.PriorityDequeue.ItemAndIndex

container

Source line 260

Fields

item: T
index: usize

std.priority_dequeue.PriorityDequeue.iterator

function

Source line 411

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

pub fn iterator(self: *Self) Iterator

Parameters

self: *Self

std.priority_dequeue.PriorityDequeue.Iterator

container

Source line 392

Fields

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

std.priority_dequeue.PriorityDequeue.Iterator.next

function

Source line 396

pub fn next(it: *Iterator) ?T

Parameters

it: *Iterator

std.priority_dequeue.PriorityDequeue.Iterator.reset

function

Source line 403

pub fn reset(it: *Iterator) void

Parameters

it: *Iterator

std.priority_dequeue.PriorityDequeue.maxIndex

function

Source line 153

fn maxIndex(self: *const Self) ?usize

Parameters

self: *const Self

std.priority_dequeue.PriorityDequeue.nextIsMinLayer

function

Source line 81

fn nextIsMinLayer(self: *const Self) bool

Parameters

self: *const Self

std.priority_dequeue.PriorityDequeue.parentIndex

function

Source line 435

fn parentIndex(index: usize) usize

Parameters

index: usize

std.priority_dequeue.PriorityDequeue.peekMax

function

Source line 146

Look at the largest element in the dequeue. Returns null if empty.

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

Parameters

self: *const Self

std.priority_dequeue.PriorityDequeue.peekMin

function

Source line 140

Look at the smallest element in the dequeue. Returns null if empty.

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

Parameters

self: *const Self

std.priority_dequeue.PriorityDequeue.popIndex

function

Source line 173

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_dequeue.PriorityDequeue.popMax

function

Source line 166

Remove and return the largest element from the dequeue, or null if empty

pub fn popMax(self: *Self) ?T

Parameters

self: *Self

std.priority_dequeue.PriorityDequeue.popMin

function

Source line 161

Remove and return the smallest element from the dequeue, or null if empty

pub fn popMin(self: *Self) ?T

Parameters

self: *Self

std.priority_dequeue.PriorityDequeue.push

function

Source line 49

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_dequeue.PriorityDequeue.pushSlice

function

Source line 55

Add each element in items to the dequeue.

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

Parameters

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

std.priority_dequeue.PriorityDequeue.pushUnchecked

function

Source line 62

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

Parameters

self: *Self
elem: T

std.priority_dequeue.PriorityDequeue.Self

alias

Source line 20

Alias of std.priority_dequeue.PriorityDequeue

std.priority_dequeue.PriorityDequeue.shrinkAndFree

function

Source line 365

Reduce allocated capacity to new_len.

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

Parameters

self: *Self
allocator: Allocator
new_len: usize

std.priority_dequeue.PriorityDequeue.siftDown

function

Source line 185

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

Parameters

self: *Self
index: usize

std.priority_dequeue.PriorityDequeue.siftUp

function

Source line 113

fn siftUp(self: *Self, start: StartIndexAndLayer) void

Parameters

self: *Self
start: StartIndexAndLayer

std.priority_dequeue.PriorityDequeue.StartIndexAndLayer

container

Source line 85

Fields

index: usize
min_layer: bool

std.priority_dequeue.PriorityDequeue.swapIfParentIsBetter

function

Source line 250

fn swapIfParentIsBetter(self: *Self, child: T, child_index: usize, target_order: Order) void

Parameters

self: *Self
child: T
child_index: usize
target_order: Order

std.priority_dequeue.PriorityDequeue.update

function

Source line 379

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

Parameters

self: *Self
elem: T
new_elem: T

std.priority_dequeue.std

alias

Source line 1

Alias of std

std.priority_dequeue.testing

alias

Source line 5

Alias of std.testing

std.priority_dequeue.uniqueLessThan

function

Source line 1071

fn uniqueLessThan(_: void, a: u32, b: u32) Order

Parameters

_: void
a: u32
b: u32
Source code

std/priority_dequeue.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 Dequeue for storing generic data. Initialize with `init`.
/// Provide `compareFn` that returns `Order.lt` when its second
/// argument should get min-popped before its third argument,
/// `Order.eq` if the arguments are of equal priority, or `Order.gt`
/// if the third argument should be min-popped second.
/// Popping the max element works in reverse. For example,
/// to make `popMin` return the smallest number, provide
/// `fn lessThan(context: void, a: T, b: T) Order { _ = context; return std.math.order(a, b); }`
pub fn PriorityDequeue(comptime T: type, comptime Context: type, comptime compareFn: fn (context: Context, a: T, b: T) Order) type {
    return struct {
        const Self = @This();

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

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

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

        /// Free memory used by the dequeue.
        pub fn deinit(self: *Self, allocator: Allocator) void {
            allocator.free(self.items);
            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);
        }

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

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

            if (self.len > 0) {
                const start = self.getStartForSiftUp(elem, self.len);
                self.siftUp(start);
            }

            self.len += 1;
        }

        fn isMinLayer(index: usize) bool {
            // In the min-max heap structure:
            // The first element is on a min layer;
            // next two are on a max layer;
            // next four are on a min layer, and so on.
            return 1 == @clz(index +% 1) & 1;
        }

        fn nextIsMinLayer(self: *const Self) bool {
            return isMinLayer(self.len);
        }

        const StartIndexAndLayer = struct {
            index: usize,
            min_layer: bool,
        };

        fn getStartForSiftUp(self: *const Self, child: T, index: usize) StartIndexAndLayer {
            const child_index = index;
            const parent_index = parentIndex(child_index);
            const parent = self.items[parent_index];

            const min_layer = self.nextIsMinLayer();
            const order = compareFn(self.context, child, parent);
            if ((min_layer and order == .gt) or (!min_layer and order == .lt)) {
                // We must swap the item with it's parent if it is on the "wrong" layer
                self.items[parent_index] = child;
                self.items[child_index] = parent;
                return .{
                    .index = parent_index,
                    .min_layer = !min_layer,
                };
            } else {
                return .{
                    .index = child_index,
                    .min_layer = min_layer,
                };
            }
        }

        fn siftUp(self: *Self, start: StartIndexAndLayer) void {
            if (start.min_layer) {
                doSiftUp(self, start.index, .lt);
            } else {
                doSiftUp(self, start.index, .gt);
            }
        }

        fn doSiftUp(self: *Self, start_index: usize, target_order: Order) void {
            var child_index = start_index;
            while (child_index > 2) {
                const grandparent_index = grandparentIndex(child_index);
                const child = self.items[child_index];
                const grandparent = self.items[grandparent_index];

                // If the grandparent is already better or equal, we have gone as far as we need to
                if (compareFn(self.context, child, grandparent) != target_order) break;

                // Otherwise swap the item with it's grandparent
                self.items[grandparent_index] = child;
                self.items[child_index] = grandparent;
                child_index = grandparent_index;
            }
        }

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

        /// Look at the largest element in the dequeue. Returns
        /// `null` if empty.
        pub fn peekMax(self: *const Self) ?T {
            if (self.len == 0) return null;
            if (self.len == 1) return self.items[0];
            if (self.len == 2) return self.items[1];
            return self.bestItemAtIndices(1, 2, .gt).item;
        }

        fn maxIndex(self: *const Self) ?usize {
            if (self.len == 0) return null;
            if (self.len == 1) return 0;
            if (self.len == 2) return 1;
            return self.bestItemAtIndices(1, 2, .gt).index;
        }

        /// Remove and return the smallest element from the dequeue, or `null` if empty
        pub fn popMin(self: *Self) ?T {
            return if (self.len > 0) self.popIndex(0) else null;
        }

        /// Remove and return the largest element from the dequeue, or `null` if empty
        pub fn popMax(self: *Self) ?T {
            return if (self.len > 0) self.popIndex(self.maxIndex().?) 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.len > index);
            const item = self.items[index];
            const last = self.items[self.len - 1];

            self.items[index] = last;
            self.len -= 1;
            siftDown(self, index);

            return item;
        }

        fn siftDown(self: *Self, index: usize) void {
            if (isMinLayer(index)) {
                self.doSiftDown(index, .lt);
            } else {
                self.doSiftDown(index, .gt);
            }
        }

        fn doSiftDown(self: *Self, start_index: usize, target_order: Order) void {
            var index = start_index;
            const half = self.len >> 1;
            while (true) {
                const first_grandchild_index = firstGrandchildIndex(index);
                const last_grandchild_index = first_grandchild_index + 3;

                const elem = self.items[index];

                if (last_grandchild_index < self.len) {
                    // All four grandchildren exist
                    const index2 = first_grandchild_index + 1;
                    const index3 = index2 + 1;

                    // Find the best grandchild
                    const best_left = self.bestItemAtIndices(first_grandchild_index, index2, target_order);
                    const best_right = self.bestItemAtIndices(index3, last_grandchild_index, target_order);
                    const best_grandchild = self.bestItem(best_left, best_right, target_order);

                    // If the item is better than or equal to its best grandchild, we are done
                    if (compareFn(self.context, best_grandchild.item, elem) != target_order) return;

                    // Otherwise, swap them
                    self.items[best_grandchild.index] = elem;
                    self.items[index] = best_grandchild.item;
                    index = best_grandchild.index;

                    // We might need to swap the element with it's parent
                    self.swapIfParentIsBetter(elem, index, target_order);
                } else {
                    // The children or grandchildren are the last layer
                    const first_child_index = firstChildIndex(index);
                    if (first_child_index >= self.len) return;

                    const best_descendent = self.bestDescendent(first_child_index, first_grandchild_index, target_order);

                    // If the item is better than or equal to its best descendant, we are done
                    if (compareFn(self.context, best_descendent.item, elem) != target_order) return;

                    // Otherwise swap them
                    self.items[best_descendent.index] = elem;
                    self.items[index] = best_descendent.item;
                    index = best_descendent.index;

                    // If we didn't swap a grandchild, we are done
                    if (index < first_grandchild_index) return;

                    // We might need to swap the element with it's parent
                    self.swapIfParentIsBetter(elem, index, target_order);
                    return;
                }

                // If we are now in the last layer, we are done
                if (index >= half) return;
            }
        }

        fn swapIfParentIsBetter(self: *Self, child: T, child_index: usize, target_order: Order) void {
            const parent_index = parentIndex(child_index);
            const parent = self.items[parent_index];

            if (compareFn(self.context, parent, child) == target_order) {
                self.items[parent_index] = child;
                self.items[child_index] = parent;
            }
        }

        const ItemAndIndex = struct {
            item: T,
            index: usize,
        };

        fn getItem(self: *const Self, index: usize) ItemAndIndex {
            return .{
                .item = self.items[index],
                .index = index,
            };
        }

        fn bestItem(self: *const Self, item1: ItemAndIndex, item2: ItemAndIndex, target_order: Order) ItemAndIndex {
            if (compareFn(self.context, item1.item, item2.item) == target_order) {
                return item1;
            } else {
                return item2;
            }
        }

        fn bestItemAtIndices(self: *const Self, index1: usize, index2: usize, target_order: Order) ItemAndIndex {
            const item1 = self.getItem(index1);
            const item2 = self.getItem(index2);
            return self.bestItem(item1, item2, target_order);
        }

        fn bestDescendent(self: *const Self, first_child_index: usize, first_grandchild_index: usize, target_order: Order) ItemAndIndex {
            const second_child_index = first_child_index + 1;
            if (first_grandchild_index >= self.len) {
                // No grandchildren, find the best child (second may not exist)
                if (second_child_index >= self.len) {
                    return .{
                        .item = self.items[first_child_index],
                        .index = first_child_index,
                    };
                } else {
                    return self.bestItemAtIndices(first_child_index, second_child_index, target_order);
                }
            }

            const second_grandchild_index = first_grandchild_index + 1;
            if (second_grandchild_index >= self.len) {
                // One grandchild, so we know there is a second child. Compare first grandchild and second child
                return self.bestItemAtIndices(first_grandchild_index, second_child_index, target_order);
            }

            const best_left_grandchild_index = self.bestItemAtIndices(first_grandchild_index, second_grandchild_index, target_order).index;
            const third_grandchild_index = second_grandchild_index + 1;
            if (third_grandchild_index >= self.len) {
                // Two grandchildren, and we know the best. Compare this to second child.
                return self.bestItemAtIndices(best_left_grandchild_index, second_child_index, target_order);
            } else {
                // Three grandchildren, compare the min of the first two with the third
                return self.bestItemAtIndices(best_left_grandchild_index, third_grandchild_index, target_order);
            }
        }

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

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

        /// Dequeue takes ownership of the passed in slice. The slice must be de-initialize
        /// with `deinit`.
        pub fn fromOwnedSlice(items: []T, context: Context) Self {
            var queue = Self{
                .items = items,
                .len = items.len,
                .context = context,
            };

            if (queue.len <= 1) return queue;

            const half = (queue.len >> 1) - 1;
            var i: usize = 0;
            while (i <= half) : (i += 1) {
                const index = half - i;
                queue.siftDown(index);
            }
            return queue;
        }

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

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

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

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

            self.items = allocator.realloc(self.items[0..], new_len) catch |e| switch (e) {
                error.OutOfMemory => { // no problem, capacity is still correct then.
                    self.items.len = new_len;
                    return;
                },
            };
        }

        pub fn update(self: *Self, elem: T, new_elem: T) !void {
            const old_index = blk: {
                var idx: usize = 0;
                while (idx < self.len) : (idx += 1) {
                    const item = self.items[idx];
                    if (compareFn(self.context, item, elem) == .eq) break :blk idx;
                }
                return error.ElementNotFound;
            };
            _ = self.popIndex(old_index);
            self.pushUnchecked(new_elem);
        }

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

            pub fn next(it: *Iterator) ?T {
                if (it.count >= it.queue.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 queue is modified.
        pub fn iterator(self: *Self) Iterator {
            return Iterator{
                .queue = self,
                .count = 0,
            };
        }

        fn dump(self: *Self) void {
            const print = std.debug.print;
            print("{{ ", .{});
            print("items: ", .{});
            for (self.items, 0..) |e, i| {
                if (i >= self.len) break;
                print("{}, ", .{e});
            }
            print("array: ", .{});
            for (self.items) |e| {
                print("{}, ", .{e});
            }
            print("len: {} ", .{self.len});
            print("capacity: {}", .{self.capacity()});
            print(" }}\n", .{});
        }

        fn parentIndex(index: usize) usize {
            return (index - 1) >> 1;
        }

        fn grandparentIndex(index: usize) usize {
            return parentIndex(parentIndex(index));
        }

        fn firstChildIndex(index: usize) usize {
            return (index << 1) + 1;
        }

        fn firstGrandchildIndex(index: usize) usize {
            return firstChildIndex(firstChildIndex(index));
        }
    };
}

/// If a min heap is constructed from slice `{5, 8, 2, 9, 7, 1, 4, 4}` using this
/// method, then the elements will be in order: {1, 2, 4, 4, 5, 7, 8, 9}
fn lessThanComparison(context: void, a: u32, b: u32) Order {
    _ = context;
    return std.math.order(a, b);
}

/// Elements with lower priority will be removed first
const MinHeap = PriorityDequeue(u32, void, lessThanComparison);

test "push and pop min in min heap" {
    const gpa = std.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.popMin());
    try expectEqual(@as(u32, 12), queue.popMin());
    try expectEqual(@as(u32, 13), queue.popMin());
    try expectEqual(@as(u32, 23), queue.popMin());
    try expectEqual(@as(u32, 25), queue.popMin());
    try expectEqual(@as(u32, 54), queue.popMin());
}

test "push and pop min structs" {
    const gpa = std.testing.allocator;

    const S = struct {
        size: u32,
    };
    var queue = PriorityDequeue(S, void, struct {
        fn order(context: void, a: S, b: S) Order {
            _ = context;
            return std.math.order(a.size, b.size);
        }
    }.order).initContext({});
    defer queue.deinit(gpa);

    try queue.push(gpa, .{ .size = 54 });
    try queue.push(gpa, .{ .size = 12 });
    try queue.push(gpa, .{ .size = 7 });
    try queue.push(gpa, .{ .size = 23 });
    try queue.push(gpa, .{ .size = 25 });
    try queue.push(gpa, .{ .size = 13 });

    try expectEqual(@as(u32, 7), queue.popMin().?.size);
    try expectEqual(@as(u32, 12), queue.popMin().?.size);
    try expectEqual(@as(u32, 13), queue.popMin().?.size);
    try expectEqual(@as(u32, 23), queue.popMin().?.size);
    try expectEqual(@as(u32, 25), queue.popMin().?.size);
    try expectEqual(@as(u32, 54), queue.popMin().?.size);
}

test "push and pop max in min heap" {
    const gpa = std.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, 54), queue.popMax());
    try expectEqual(@as(u32, 25), queue.popMax());
    try expectEqual(@as(u32, 23), queue.popMax());
    try expectEqual(@as(u32, 13), queue.popMax());
    try expectEqual(@as(u32, 12), queue.popMax());
    try expectEqual(@as(u32, 7), queue.popMax());
}

test "push and pop same min in min heap" {
    const gpa = std.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.popMin());
    try expectEqual(@as(u32, 1), queue.popMin());
    try expectEqual(@as(u32, 1), queue.popMin());
    try expectEqual(@as(u32, 1), queue.popMin());
    try expectEqual(@as(u32, 2), queue.popMin());
    try expectEqual(@as(u32, 2), queue.popMin());
}

test "push and pop same max in min heap" {
    const gpa = std.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, 2), queue.popMax());
    try expectEqual(@as(u32, 2), queue.popMax());
    try expectEqual(@as(u32, 1), queue.popMax());
    try expectEqual(@as(u32, 1), queue.popMax());
    try expectEqual(@as(u32, 1), queue.popMax());
    try expectEqual(@as(u32, 1), queue.popMax());
}

test "pop empty in min heap" {
    const gpa = std.testing.allocator;

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

    try expect(queue.popMin() == null);
    try expect(queue.popMax() == null);
}

test "edge case 3 elements popMin in min heap" {
    const gpa = std.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.popMin());
    try expectEqual(@as(u32, 3), queue.popMin());
    try expectEqual(@as(u32, 9), queue.popMin());
}

test "edge case 3 elements popmax in min heap" {
    const gpa = std.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, 9), queue.popMax());
    try expectEqual(@as(u32, 3), queue.popMax());
    try expectEqual(@as(u32, 2), queue.popMax());
}

test "peekMin in min heap" {
    const gpa = std.testing.allocator;

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

    try expect(queue.peekMin() == null);

    try queue.push(gpa, 9);
    try queue.push(gpa, 3);
    try queue.push(gpa, 2);

    try expect(queue.peekMin().? == 2);
    try expect(queue.peekMin().? == 2);
}

test "peekMax in min heap" {
    const gpa = std.testing.allocator;

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

    try expect(queue.peekMin() == null);

    try queue.push(gpa, 9);
    try queue.push(gpa, 3);
    try queue.push(gpa, 2);

    try expect(queue.peekMax().? == 9);
    try expect(queue.peekMax().? == 9);
}

test "sift up with odd indices and popMin in min heap" {
    const gpa = std.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.popMin());
    }
}

test "sift up with odd indices and popMax in min heap" {
    const gpa = std.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{ 25, 24, 24, 22, 21, 16, 15, 15, 14, 13, 12, 11, 7, 7, 6, 5, 2, 1 };
    for (sorted_items) |e| {
        try expectEqual(e, queue.popMax());
    }
}

test "pushSlice in min heap and popMin" {
    const gpa = std.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.popMin());
    }
}

test "pushSlice in min heap and popMax" {
    const gpa = std.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{ 25, 24, 24, 22, 21, 16, 15, 15, 14, 13, 12, 11, 7, 7, 6, 5, 2, 1 };
    for (sorted_items) |e| {
        try expectEqual(e, queue.popMax());
    }
}

test "fromOwnedSlice trivial case 0 min heap" {
    const gpa = std.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.len);
    try expect(queue.popMin() == null);
}

test "fromOwnedSlice trivial case 1 min heap" {
    const gpa = std.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.len);
    try expectEqual(items[0], queue.popMin());
    try expect(queue.popMin() == null);
}

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

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

    var queue: MinHeap = .fromOwnedSlice(queue_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.popMin());
    }
}

test "update and popMin in min heap" {
    const gpa = std.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.popMin());
    try expectEqual(@as(u32, 4), queue.popMin());
    try expectEqual(@as(u32, 5), queue.popMin());
}

test "update same element and popMin in min heap" {
    const gpa = std.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.popMin());
    try expectEqual(@as(u32, 2), queue.popMin());
    try expectEqual(@as(u32, 4), queue.popMin());
    try expectEqual(@as(u32, 5), queue.popMin());
}

test "update and popMax in min heap" {
    const gpa = std.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, 1);
    try queue.update(11, 4);

    try expectEqual(@as(u32, 5), queue.popMax());
    try expectEqual(@as(u32, 4), queue.popMax());
    try expectEqual(@as(u32, 1), queue.popMax());
}

test "update same element and popMax in min heap" {
    const gpa = std.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, 5), queue.popMax());
    try expectEqual(@as(u32, 4), queue.popMax());
    try expectEqual(@as(u32, 2), queue.popMax());
    try expectEqual(@as(u32, 1), queue.popMax());
}

test "update after pop in min heap" {
    const gpa = std.testing.allocator;

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

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

test "min heap iterator" {
    const gpa = std.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 "pop at index in min heap" {
    const gpa = std.testing.allocator;

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

    try queue.push(gpa, 3);
    try queue.push(gpa, 2);
    try queue.push(gpa, 1);

    var it = queue.iterator();
    var elem = it.next();
    var idx: usize = 0;
    const two_idx = while (elem != null) : (elem = it.next()) {
        if (elem.? == 2)
            break idx;
        idx += 1;
    } else unreachable;

    try expectEqual(queue.popIndex(two_idx), 2);
    try expectEqual(queue.popMin(), 1);
    try expectEqual(queue.popMin(), 3);
    try expectEqual(queue.popMin(), null);
}

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

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

    var it = queue.iterator();

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

test "min heap shrinkAndFree" {
    const gpa = std.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.len);

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

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

test "fuzz testing min" {
    var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
    const random = prng.random();

    const test_case_count = 100;
    const queue_size = 1_000;

    var i: usize = 0;
    while (i < test_case_count) : (i += 1) {
        try fuzzTestMin(random, queue_size);
    }
}

fn fuzzTestMin(rng: std.Random, comptime queue_size: usize) !void {
    const gpa = std.testing.allocator;

    const items = try generateRandomSlice(gpa, rng, queue_size);

    var queue: MinHeap = .fromOwnedSlice(items, {});
    defer queue.deinit(gpa);

    var last_removed: ?u32 = null;
    while (queue.popMin()) |next| {
        if (last_removed) |last| {
            try expect(last <= next);
        }
        last_removed = next;
    }
}

test "fuzz testing max" {
    var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
    const random = prng.random();

    const test_case_count = 100;
    const queue_size = 1_000;

    var i: usize = 0;
    while (i < test_case_count) : (i += 1) {
        try fuzzTestMax(random, queue_size);
    }
}

fn fuzzTestMax(rng: std.Random, queue_size: usize) !void {
    const gpa = std.testing.allocator;

    const items = try generateRandomSlice(gpa, rng, queue_size);

    var queue: MinHeap = .fromOwnedSlice(items, {});
    defer queue.deinit(gpa);

    var last_removed: ?u32 = null;
    while (queue.popMax()) |next| {
        if (last_removed) |last| {
            try expect(last >= next);
        }
        last_removed = next;
    }
}

test "fuzz testing min and max" {
    var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
    const random = prng.random();

    const test_case_count = 100;
    const queue_size = 1_000;

    var i: usize = 0;
    while (i < test_case_count) : (i += 1) {
        try fuzzTestMinMax(random, queue_size);
    }
}

fn fuzzTestMinMax(rng: std.Random, queue_size: usize) !void {
    const gpa = std.testing.allocator;

    const items = try generateRandomSlice(gpa, rng, queue_size);

    var queue: MinHeap = .fromOwnedSlice(items, {});
    defer queue.deinit(gpa);

    var last_min: ?u32 = null;
    var last_max: ?u32 = null;
    var i: usize = 0;
    while (i < queue_size) : (i += 1) {
        if (i % 2 == 0) {
            const next = queue.popMin().?;
            if (last_min) |last| {
                try expect(last <= next);
            }
            last_min = next;
        } else {
            const next = queue.popMax().?;
            if (last_max) |last| {
                try expect(last >= next);
            }
            last_max = next;
        }
    }
}

fn generateRandomSlice(allocator: std.mem.Allocator, rng: std.Random, size: usize) ![]u32 {
    var array = std.array_list.Managed(u32).init(allocator);
    try array.ensureTotalCapacity(size);

    var i: usize = 0;
    while (i < size) : (i += 1) {
        const elem = rng.int(u32);
        try array.append(elem);
    }

    return array.toOwnedSlice();
}

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

const MinHeapWithContext = PriorityDequeue(usize, []const u32, contextLessThanComparison);

test "push and pop" {
    const gpa = std.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.popMin());
    try expectEqual(@as(usize, 5), queue.popMax());
    try expectEqual(@as(usize, 3), queue.popMin());
    try expectEqual(@as(usize, 0), queue.popMax());
    try expectEqual(@as(usize, 4), queue.popMin());
    try expectEqual(@as(usize, 2), queue.popMax());
    try expectEqual(@as(usize, 1), queue.popMin());
}

var all_cmps_unique = true;

test "don't compare a value to a copy of itself" {
    const gpa = std.testing.allocator;

    var depq = PriorityDequeue(u32, void, struct {
        fn uniqueLessThan(_: void, a: u32, b: u32) Order {
            all_cmps_unique = all_cmps_unique and (a != b);
            return std.math.order(a, b);
        }
    }.uniqueLessThan).initContext({});
    defer depq.deinit(gpa);

    try depq.push(gpa, 1);
    try depq.push(gpa, 2);
    try depq.push(gpa, 3);
    try depq.push(gpa, 4);
    try depq.push(gpa, 5);
    try depq.push(gpa, 6);

    _ = depq.popIndex(2);
    try expectEqual(all_cmps_unique, true);
}