Day 54: std.priority_queue模块：优先队列

1. 引言：堆结构

优先队列（Priority Queue）是一种特殊的队列，其中每个元素都有一个关联的“优先级”。与普通队列的“先进先出”（FIFO）不同，优先队列中的元素是按照它们的优先级顺序出队的。通常，优先级最高的元素最先出队。

在底层，std.PriorityQueue是使用二叉堆（Binary Heap）实现的。这是一种树形数据结构，能保证在O(log n)时间内完成插入和删除最高优先级元素的操作，而在O(1)时间内查看最高优先级的元素。

2. 定义：PriorityQueue(T, Context)

std.PriorityQueue是一个泛型结构体，需要两个编译期参数：

• T: 队列中存储的元素类型。
• Context: 一个上下文类型，它必须提供一个lessThan(context: Context, a: T, b: T) bool函数，用于比较两个元素的优先级。lessThan(a, b)返回true表示a的优先级高于b。

初始化一个PriorityQueue需要一个分配器和上下文实例：

const std = @import("std");

// 定义一个上下文，用于比较i32，值越小优先级越高
const MinIntContext = struct {
    pub fn lessThan(_: @This(), a: i32, b: i32) bool {
        return a < b;
    }
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var pq = std.PriorityQueue(i32, MinIntContext).init(allocator, .{});
    defer pq.deinit();

    // ... 使用pq
}

3. 操作：add, remove, peek

优先队列的核心操作包括添加元素、移除最高优先级元素和查看最高优先级元素。

• add(item: T) !void: 向队列中添加一个新元素。它将被放置在堆中的正确位置以维持堆的属性。
• remove(): 移除并返回队列中优先级最高的元素。
• peek(): 返回对优先级最高的元素的引用，但不从队列中移除它。
• len: 获取队列中元素的数量。

// ...接上文

try pq.add(30);
try pq.add(10);
try pq.add(20);

std.debug.print("Top priority item: {d}\n", .{pq.peek().?}); // 10

while (pq.len > 0) {
    const item = pq.remove();
    std.debug.print("Removed: {d}\n", .{item});
}
// 输出将是: 10, 20, 30

4. 示例：Dijkstra算法的一部分

优先队列是许多图算法的关键，例如Dijkstra最短路径算法。在Dijkstra中，优先队列用于存储待访问的节点，并按其到源点的已知最短距离进行排序。

const std = @import("std");

const Node = struct { id: u32, dist: u32 };

const NodeContext = struct {
    pub fn lessThan(_: @This(), a: Node, b: Node) bool {
        return a.dist < b.dist;
    }
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var nodes_to_visit = std.PriorityQueue(Node, NodeContext).init(allocator, .{});
    defer nodes_to_visit.deinit();

    try nodes_to_visit.add(.{ .id = 0, .dist = 0 });
    try nodes_to_visit.add(.{ .id = 1, .dist = 10 });
    try nodes_to_visit.add(.{ .id = 2, .dist = 5 });

    const current = nodes_to_visit.remove();
    std.debug.print("Visiting node {d} with distance {d}\n", .{current.id, current.dist}); // Node 0, dist 0

    const next = nodes_to_visit.remove();
    std.debug.print("Visiting node {d} with distance {d}\n", .{next.id, next.dist}); // Node 2, dist 5
}

5. 实践练习：任务调度器

创建一个简单的任务调度器。任务由一个描述和一个优先级（整数，值越小优先级越高）组成。程序应该能添加任务，然后按优先级顺序执行它们。

点击查看参考实现

const std = @import("std");

const Task = struct { name: []const u8, priority: u8 };

const TaskContext = struct {
    pub fn lessThan(_: @This(), a: Task, b: Task) bool {
        return a.priority < b.priority;
    }
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var scheduler = std.PriorityQueue(Task, TaskContext).init(allocator, .{});
    defer scheduler.deinit();

    try scheduler.add(.{ .name = "Send emails", .priority = 3 });
    try scheduler.add(.{ .name = "Run backups", .priority = 1 });
    try scheduler.add(.{ .name = "Process payments", .priority = 0 });

    while (scheduler.len > 0) {
        const task = scheduler.remove();
        std.debug.print("Executing task: '{s}' (priority {d})\n", .{task.name, task.priority});
    }
}

6. 常见问题

• 比较器（Context）如何工作？ lessThan函数是优先队列的核心。lessThan(a, b)返回true意味着a应该比b更早出队。如果你想实现一个最大堆（值越大优先级越高），你只需在lessThan中返回a > b。

• 优先队列是稳定的吗？ std.PriorityQueue的实现不保证稳定性。如果两个元素有相同的优先级，它们出队的顺序是不确定的。

• 容量管理 与ArrayList类似，PriorityQueue在需要时会自动扩容。它内部使用一个ArrayList来存储堆，因此也具有类似的摊销性能特征。

7. 总结：二叉堆的力量

std.PriorityQueue是Zig标准库中一个强大而高效的工具，适用于任何需要按特定顺序处理元素的场景。通过其泛型设计和可定制的比较上下文，它可以轻松适应各种数据类型和优先级规则。理解其基于二叉堆的实现有助于更好地预测其性能，并将其应用于从算法竞赛到实际系统开发的各种问题中。