跳转到内容

std.priority_dequeue

标准库Zig 0.17.1官方原文
源码std/priority_dequeue.zig

第 1 行

std.priority_dequeue.all_cmps_unique

变量

第 1065 行

std.priority_dequeue.Allocator

别名

第 2 行

别名目标 std.mem.Allocator

std.priority_dequeue.assert

别名

第 3 行

别名目标 std.debug.assert

std.priority_dequeue.contextLessThanComparison

函数

第 1035 行

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

参数

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

std.priority_dequeue.expect

别名

第 6 行

别名目标 std.testing.expect

std.priority_dequeue.expectEqual

别名

第 7 行

别名目标 std.testing.expectEqual

std.priority_dequeue.expectError

别名

第 8 行

别名目标 std.testing.expectError

std.priority_dequeue.fuzzTestMax

函数

第 964 行

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

参数

rng: std.Random
queue_size: usize

std.priority_dequeue.fuzzTestMin

函数

第 934 行

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

参数

rng: std.Random
queue_size: usize

std.priority_dequeue.fuzzTestMinMax

函数

第 994 行

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

参数

rng: std.Random
queue_size: usize

std.priority_dequeue.generateRandomSlice

函数

第 1022 行

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

参数

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

std.priority_dequeue.lessThanComparison

函数

第 455 行

如果使用此方法从切片 {5, 8, 2, 9, 7, 1, 4, 4} 构造最小堆, 则元素的顺序为:{1, 2, 4, 4, 5, 7, 8, 9}

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

参数

context: void
a: u32
b: u32

std.priority_dequeue.MinHeap

类型

第 461 行

优先级较低的元素会先被移除。

std.priority_dequeue.MinHeapWithContext

类型

第 1039 行

std.priority_dequeue.order

函数

第 491 行

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

参数

context: void
a: S
b: S

std.priority_dequeue.Order

别名

第 4 行

别名目标 std.math.Order

std.priority_dequeue.PriorityDequeue

类型函数

第 18 行

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

参数

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

字段

items: []T
len: usize
context: Context

std.priority_dequeue.PriorityDequeue.bestDescendent

函数

第 286 行

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

参数

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

std.priority_dequeue.PriorityDequeue.bestItem

函数

第 272 行

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

参数

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

std.priority_dequeue.PriorityDequeue.bestItemAtIndices

函数

第 280 行

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

参数

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

std.priority_dequeue.PriorityDequeue.capacity

函数

第 324 行

返回在再次分配内存之前, 双端队列还可添加的元素数量。

pub fn capacity(self: *const Self) usize

参数

self: *const Self

std.priority_dequeue.PriorityDequeue.count

函数

第 318 行

返回双端队列中的剩余元素数

pub fn count(self: *const Self) usize

参数

self: *const Self

std.priority_dequeue.PriorityDequeue.deinit

函数

第 43 行

释放双端队列使用的内存。

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

参数

self: *Self
allocator: Allocator

std.priority_dequeue.PriorityDequeue.doSiftDown

函数

第 193 行

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

参数

self: *Self
start_index: usize
target_order: Order

std.priority_dequeue.PriorityDequeue.doSiftUp

函数

第 121 行

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

参数

self: *Self
start_index: usize
target_order: Order

std.priority_dequeue.PriorityDequeue.dump

函数

第 418 行

fn dump(self: *Self) void

参数

self: *Self

std.priority_dequeue.PriorityDequeue.empty

常量

第 27 行

不含元素的优先双端队列。

Self

std.priority_dequeue.PriorityDequeue.ensureTotalCapacity

函数

第 349 行

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

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

参数

self: *Self
allocator: Allocator
new_capacity: usize

std.priority_dequeue.PriorityDequeue.ensureUnusedCapacity

函数

第 360 行

确保双端队列至少还能容纳 additional_count 个额外元素。

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

参数

self: *Self
allocator: Allocator
additional_count: usize

std.priority_dequeue.PriorityDequeue.firstChildIndex

函数

第 443 行

fn firstChildIndex(index: usize) usize

参数

index: usize

std.priority_dequeue.PriorityDequeue.firstGrandchildIndex

函数

第 447 行

fn firstGrandchildIndex(index: usize) usize

参数

index: usize

std.priority_dequeue.PriorityDequeue.fromOwnedSlice

函数

第 330 行

Dequeue 接管传入切片的所有权。必须使用 deinit 反初始化该切片。

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

参数

items: []T
context: Context

std.priority_dequeue.PriorityDequeue.getItem

函数

第 265 行

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

参数

self: *const Self
index: usize

std.priority_dequeue.PriorityDequeue.getStartForSiftUp

函数

第 90 行

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

参数

self: *const Self
child: T
index: usize

std.priority_dequeue.PriorityDequeue.grandparentIndex

函数

第 439 行

fn grandparentIndex(index: usize) usize

参数

index: usize

std.priority_dequeue.PriorityDequeue.initContext

函数

第 34 行

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

pub fn initContext(context: Context) Self

参数

context: Context

std.priority_dequeue.PriorityDequeue.isMinLayer

函数

第 73 行

fn isMinLayer(index: usize) bool

参数

index: usize

std.priority_dequeue.PriorityDequeue.ItemAndIndex

容器

第 260 行

字段

item: T
index: usize

std.priority_dequeue.PriorityDequeue.iterator

函数

第 411 行

返回遍历队列但不消费队列的迭代器。迭代顺序可能不同于优先级顺序。队列修改后失效。

pub fn iterator(self: *Self) Iterator

参数

self: *Self

std.priority_dequeue.PriorityDequeue.Iterator

容器

第 392 行

字段

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

std.priority_dequeue.PriorityDequeue.Iterator.next

函数

第 396 行

pub fn next(it: *Iterator) ?T

参数

it: *Iterator

std.priority_dequeue.PriorityDequeue.Iterator.reset

函数

第 403 行

pub fn reset(it: *Iterator) void

参数

it: *Iterator

std.priority_dequeue.PriorityDequeue.maxIndex

函数

第 153 行

fn maxIndex(self: *const Self) ?usize

参数

self: *const Self

std.priority_dequeue.PriorityDequeue.nextIsMinLayer

函数

第 81 行

fn nextIsMinLayer(self: *const Self) bool

参数

self: *const Self

std.priority_dequeue.PriorityDequeue.parentIndex

函数

第 435 行

fn parentIndex(index: usize) usize

参数

index: usize

std.priority_dequeue.PriorityDequeue.peekMax

函数

第 146 行

查看双端队列中的最大元素。若为空,则返回 null。

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

参数

self: *const Self

std.priority_dequeue.PriorityDequeue.peekMin

函数

第 140 行

查看双端队列中的最小元素。为空则返回 null。

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

参数

self: *const Self

std.priority_dequeue.PriorityDequeue.popIndex

函数

第 173 行

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

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

参数

self: *Self
index: usize

std.priority_dequeue.PriorityDequeue.popMax

函数

第 166 行

移除并返回双端队列中的最大元素;为空则返回 null

pub fn popMax(self: *Self) ?T

参数

self: *Self

std.priority_dequeue.PriorityDequeue.popMin

函数

第 161 行

从双端队列移除并返回最小元素;若为空,则返回 null

pub fn popMin(self: *Self) ?T

参数

self: *Self

std.priority_dequeue.PriorityDequeue.push

函数

第 49 行

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

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

参数

self: *Self
allocator: Allocator
elem: T

std.priority_dequeue.PriorityDequeue.pushSlice

函数

第 55 行

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

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

参数

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

std.priority_dequeue.PriorityDequeue.pushUnchecked

函数

第 62 行

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

参数

self: *Self
elem: T

std.priority_dequeue.PriorityDequeue.Self

别名

第 20 行

别名目标 std.priority_dequeue.PriorityDequeue

std.priority_dequeue.PriorityDequeue.shrinkAndFree

函数

第 365 行

将已分配容量减少至 new_len。

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

参数

self: *Self
allocator: Allocator
new_len: usize

std.priority_dequeue.PriorityDequeue.siftDown

函数

第 185 行

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

参数

self: *Self
index: usize

std.priority_dequeue.PriorityDequeue.siftUp

函数

第 113 行

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

参数

self: *Self
start: StartIndexAndLayer

std.priority_dequeue.PriorityDequeue.StartIndexAndLayer

容器

第 85 行

字段

index: usize
min_layer: bool

std.priority_dequeue.PriorityDequeue.swapIfParentIsBetter

函数

第 250 行

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

参数

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

std.priority_dequeue.PriorityDequeue.update

函数

第 379 行

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

参数

self: *Self
elem: T
new_elem: T

std.priority_dequeue.std

别名

第 1 行

别名目标 std

std.priority_dequeue.testing

别名

第 5 行

别名目标 std.testing

std.priority_dequeue.uniqueLessThan

函数

第 1071 行

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

参数

_: void
a: u32
b: u32
源码

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;

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

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

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

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

        /// 插入新元素并维持优先级。
        pub fn push(self: *Self, allocator: Allocator, elem: T) !void {
            try self.ensureUnusedCapacity(allocator, 1);
            pushUnchecked(self, elem);
        }

        /// 将 `items` 中每个元素加入双端队列。
        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 {
            // 在最小最大堆结构中:
            // 首个元素位于最小层;
            // 接下来两个元素位于最大层;
            // 再接下来四个元素位于最小层,依此类推。
            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)) {
                // 若元素处于“错误”层,必须将其与父节点交换
                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 (compareFn(self.context, child, grandparent) != target_order) break;

                // 否则将条目与其祖父节点交换
                self.items[grandparent_index] = child;
                self.items[child_index] = grandparent;
                child_index = grandparent_index;
            }
        }

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

        /// 查看双端队列中的最大元素。若为空,则返回 `null`。
        ///
        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;
        }

        /// 从双端队列移除并返回最小元素;若为空,则返回 `null`
        pub fn popMin(self: *Self) ?T {
            return if (self.len > 0) self.popIndex(0) else null;
        }

        /// 移除并返回双端队列中的最大元素;为空则返回 `null`
        pub fn popMax(self: *Self) ?T {
            return if (self.len > 0) self.popIndex(self.maxIndex().?) else null;
        }

        /// 移除并返回索引处的元素。索引顺序
        /// 与迭代器相同,不一定是优先级
        /// 顺序。
        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) {
                    // 四个孙节点均存在
                    const index2 = first_grandchild_index + 1;
                    const index3 = index2 + 1;

                    // 寻找最合适的孙节点
                    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 (compareFn(self.context, best_grandchild.item, elem) != target_order) return;

                    // 否则交换两者
                    self.items[best_grandchild.index] = elem;
                    self.items[index] = best_grandchild.item;
                    index = best_grandchild.index;

                    // 可能需要将该元素与其父元素交换
                    self.swapIfParentIsBetter(elem, index, target_order);
                } else {
                    // 子节点或孙节点已是最后一层。
                    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 (compareFn(self.context, best_descendent.item, elem) != target_order) return;

                    // 否则交换两者
                    self.items[best_descendent.index] = elem;
                    self.items[index] = best_descendent.item;
                    index = best_descendent.index;

                    // 若未交换孙节点,则完成
                    if (index < first_grandchild_index) return;

                    // 可能需要将该元素与其父元素交换
                    self.swapIfParentIsBetter(elem, index, target_order);
                    return;
                }

                // 若当前已处于最后一层,则完成
                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) {
                // 没有孙节点,查找最佳子节点(第二个子节点可能不存在)
                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) {
                // 存在一个孙节点,因此可知存在第二个子节点。比较第一个孙节点与第二个子节点。
                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) {
                // 存在两个孙节点,且已知最佳者。将其与第二个子节点比较。
                return self.bestItemAtIndices(best_left_grandchild_index, second_child_index, target_order);
            } else {
                // 存在三个孙节点,将前两个的最小值与第三个比较。
                return self.bestItemAtIndices(best_left_grandchild_index, third_grandchild_index, target_order);
            }
        }

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

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

        /// Dequeue 接管传入切片的所有权。必须使用 `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;
        }

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

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

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

            // 不能缩小到当前队列大小以下,否则会破坏堆性质
            assert(new_len >= self.len);

            self.items = allocator.realloc(self.items[0..], new_len) catch |e| switch (e) {
                error.OutOfMemory => { // 没有问题,此时容量仍正确。
                    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;
            }
        };

        /// 返回遍历队列但不消费队列的迭代器。迭代顺序可能不同于优先级顺序。队列修改后失效。
        ///
        ///
        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));
        }
    };
}

/// 如果使用此方法从切片 `{5, 8, 2, 9, 7, 1, 4, 4}` 构造最小堆,
/// 则元素的顺序为:{1, 2, 4, 4, 5, 7, 8, 9}
fn lessThanComparison(context: void, a: u32, b: u32) Order {
    _ = context;
    return std.math.order(a, b);
}

/// 优先级较低的元素会先被移除。
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);
}