std.priority_queue.Allocator
别名
别名目标 std.mem.Allocator
std.priority_queue.assert
别名
别名目标 std.debug.assert
std.priority_queue.contextLessThan
函数
fn contextLessThan(context: []const u32, a: usize, b: usize) Order
参数
context: []const u32
a: usize
b: usize
std.priority_queue.expect
别名
别名目标 std.testing.expect
std.priority_queue.expectEqual
别名
std.priority_queue.expectError
别名
std.priority_queue.greaterThan
函数
fn greaterThan(context: void, a: u32, b: u32) Order
参数
context: void
a: u32
b: u32
std.priority_queue.lessThan
函数
fn lessThan(context: void, a: u32, b: u32) Order
参数
context: void
a: u32
b: u32
std.priority_queue.MaxHeap
类型
std.priority_queue.MinHeap
类型
std.priority_queue.MinHeapWithContext
类型
std.priority_queue.Order
别名
别名目标 std.math.Order
std.priority_queue.PriorityQueue
类型函数
用于存储泛型数据的优先队列。用 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
参数
字段
items: []T
cap: usize
context: Context
std.priority_queue.PriorityQueue.allocatedSlice
函数
返回包含所有元素及额外容量的切片,额外容量的内存
内容为 undefined。
fn allocatedSlice(self: *const Self) []T
参数
self: *const Self
std.priority_queue.PriorityQueue.capacity
函数
返回在需要再次分配内存之前, 还能向队列添加的元素数量。
pub fn capacity(self: *const Self) usize
参数
self: *const Self
std.priority_queue.PriorityQueue.clearAndFree
函数
使所有元素指针失效。
pub fn clearAndFree(self: *Self, allocator: Allocator) void
参数
std.priority_queue.PriorityQueue.clearRetainingCapacity
函数
移除 items 切片中的全部元素。
pub fn clearRetainingCapacity(self: *Self) void
参数
self: *Self
std.priority_queue.PriorityQueue.count
函数
返回优先队列中 剩余的元素数量。
pub fn count(self: *const Self) usize
参数
self: *const Self
std.priority_queue.PriorityQueue.deinit
函数
释放队列使用的内存。
pub fn deinit(self: *Self, allocator: Allocator) void
参数
std.priority_queue.PriorityQueue.empty
常量
不含任何元素的优先队列。
Self
std.priority_queue.PriorityQueue.ensureTotalCapacity
函数
确保队列至少能容纳 new_capacity 个元素。
pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_capacity: usize) !void
参数
std.priority_queue.PriorityQueue.ensureTotalCapacityPrecise
函数
若当前容量小于 new_capacity,此函数会
修改数组,使其恰好能容纳 new_capacity 个元素。
若需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacityPrecise(self: *Self, allocator: Allocator, new_capacity: usize) !void
参数
std.priority_queue.PriorityQueue.ensureUnusedCapacity
函数
确保队列至少还能额外容纳 additional_count 个项目。
pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_count: usize) !void
参数
std.priority_queue.PriorityQueue.fromOwnedSlice
函数
PriorityQueue 取得传入切片的所有权。该切片必须由 allocator 分配。
使用 deinit 释放。
pub fn fromOwnedSlice(items: []T, context: Context) Self
参数
items: []T
context: Context
std.priority_queue.PriorityQueue.initContext
函数
使用上下文初始化并返回优先队列。
pub fn initContext(context: Context) Self
参数
context: Context
std.priority_queue.PriorityQueue.iterator
函数
返回遍历队列而不消耗元素的迭代器。 遍历顺序可能与优先级顺序不同。 堆发生修改后,迭代器失效。
pub fn iterator(self: *Self) Iterator
参数
self: *Self
std.priority_queue.PriorityQueue.Iterator
容器
字段
queue: *PriorityQueue(T, Context, compareFn)
count: usize
std.priority_queue.PriorityQueue.Iterator.next
函数
pub fn next(it: *Iterator) ?T
参数
it: *Iterator
std.priority_queue.PriorityQueue.Iterator.reset
函数
pub fn reset(it: *Iterator) void
参数
it: *Iterator
std.priority_queue.PriorityQueue.peek
函数
查看队列中优先级最高的元素。队列为空则返回
null。
pub fn peek(self: *const Self) ?T
参数
self: *const Self
std.priority_queue.PriorityQueue.pop
函数
从队列中移除并返回优先级最高的元素。
若为空,则返回 null。
pub fn pop(self: *Self) ?T
参数
self: *Self
std.priority_queue.PriorityQueue.popIndex
函数
移除并返回索引处的元素。索引顺序 与迭代器相同,不一定是优先级 顺序。
pub fn popIndex(self: *Self, index: usize) T
参数
self: *Self
index: usize
std.priority_queue.PriorityQueue.push
函数
插入新元素并维持优先级。
pub fn push(self: *Self, allocator: Allocator, elem: T) !void
参数
std.priority_queue.PriorityQueue.pushSlice
函数
将 items 中每个元素加入队列。
pub fn pushSlice(self: *Self, allocator: Allocator, items: []const T) !void
参数
std.priority_queue.PriorityQueue.pushUnchecked
函数
fn pushUnchecked(self: *Self, elem: T) void
参数
self: *Self
elem: T
std.priority_queue.PriorityQueue.Self
别名
std.priority_queue.PriorityQueue.shrinkAndFree
函数
将已分配容量减至 new_capacity。
pub fn shrinkAndFree(self: *Self, allocator: Allocator, new_capacity: usize) void
参数
std.priority_queue.PriorityQueue.siftDown
函数
fn siftDown(self: *Self, target_index: usize) void
参数
self: *Self
target_index: usize
std.priority_queue.PriorityQueue.siftUp
函数
fn siftUp(self: *Self, start_index: usize) void
参数
self: *Self
start_index: usize
std.priority_queue.PriorityQueue.update
函数
以新元素替换队列中的元素,并保持优先级。
若待更新元素不存在,则返回 error.ElementNotFound。
pub fn update(self: *Self, elem: T, new_elem: T) !void
参数
std.priority_queue.std
别名
别名目标 std
std.priority_queue.testing
别名
别名目标 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());
}