深入理解 C++ 中的优先队列与比较算子设计

核心逻辑与数学原理

std::priority_queue 是 C++ 标准模板库（STL）中的容器适配器，其底层默认基于 std::vector 实现二叉堆结构。大根堆与小根堆的动态调整，严格依赖于元素间的 全序关系（Total Ordering）。

在数学上，标准库要求自定义的比较算子必须满足 严格弱序（Strict Weak Ordering）。设比较运算符为 $\prec$，集合中的任意元素 $x, y, z$ 必须满足以下三条公理：

非自反性：$x \prec x$ 恒为假。
非对称性：若 $x \prec y$ 为真，则 $y \prec x$ 必为假。
传递性：若 $x \prec y$ 且 $y \prec z$ 为真，则 $x \prec z$ 必为真。

在 std::priority_queue 的内部逻辑中，默认使用 std::less<T> 进行元素优先级的判定。

当底层堆进行向上或向下堆化时，若 Compare(新节点, 父节点) 返回 true，则两节点不发生交换。
反直觉对位法则：大根堆的底层判定是“若父节点小于子节点则交换”。因此，当我们重载比较算子且让其在 $x < y$ 时返回 true，优先队列表现为 大根堆；反之，若在 $x > y$ 时返回 true，优先队列则逆转为 小根堆。

状态设计与算法推导

在 NOIP 实战中，往往需要维护多维属性的复合状态（例如：图论中的 (当前点, 当前最短距离)，或贪心问题中的 (截止时间, 价值)）。

1. 结构体状态设计

定义复合状态结构体 Node：

struct Node {
    int id;
    int value;
    // 多维状态扩展
};

2. 比较算子重载推导

为了实现双关键字排序（主关键字 value 从小到大，次关键字 id 从小到大，即构建小根堆），比较算子的逻辑推导如下：

若主关键字 value 不相等，则 value 较小的优先级更高。由于要构建小根堆，需要反转全序符号：当 this->value > other.value 时应返回 true。
若主关键字 value 相等，则比较次关键字 id。同理，当 this->id > other.id 时返回 true。

数学判定式可表达为：

$$\text{Compare}(A, B) = (A.\text{value} > B.\text{value}) \lor (A.\text{value} = B.\text{value} \land A.\text{id} > B.\text{id})$$

C++ 标准源码

以下为在 Linux 环境下通过 g++ -O2 严格编译的自定义结构体优先队列模板，常用于 Dijkstra 算法等图论高频场景。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

struct Node {
    int id;
    int dis;

    // 构造函数显式初始化
    Node(int _id, int _dis) : id(_id), dis(_dis) {}

    // 方式一：重载结构体内部的 < 运算符
    // 致命踩坑点：必须使用 const 修饰参数，且函数体尾部必须加 const，否则 STL 内部调用时会引发编译期错误
    bool operator<(const Node& other) const {
        if (this->dis != other.dis) {
            // 反直觉：这里写 > 代表 dis 越小优先级越高，即构建小根堆
            return this->dis > other.dis; 
        }
        return this->id > other.id;
    }
};

// 方式二：定义独立的仿函数（结构体比较算子），用于特定的 priority_queue 声明
struct CustomCompare {
    bool operator()(const Node& a, const Node& b) const {
        if (a.dis != b.dis) {
            return a.dis > b.dis; // 小根堆逻辑
        }
        return a.id > b.id;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // 使用方式一：默认使用重载的 < 运算符（注意：STL 内部默认是 less，内部用 < 判定，通过反转实现小根堆）
    std::priority_queue<Node> pq_default;

    // 使用方式二：显式传入底层容器与自定义仿函数
    std::priority_queue<Node, std::vector<Node>, CustomCompare> pq_custom;

    int n;
    if (std::cin >> n) {
        for (int i = 0; i < n; ++i) {
            int id, dis;
            std::cin >> id >> dis;
            pq_default.push(Node(id, dis));
            pq_custom.push(Node(id, dis));
        }

        std::cout << "Default PQ (Smallest dis first):\n";
        while (!pq_default.empty()) {
            Node top_node = pq_default.top();
            pq_default.pop();
            std::cout << "ID: " << top_node.id << " Dis: " << top_node.dis << "\n";
        }
    }

    return 0;
}

NOIP 实战避坑指南

重载运算符未加 const 限定符导致编译瘫痪 在重载 operator< 时，写成 bool operator<(Node& other)。由于 std::priority_queue 内部为了安全，传入的都是 const Node& 类型的常量引用。当标准库试图用 < 比较两个常量对象时，由于没有对应的 const 成员函数可用，g++ 会直接抛出几百行的 no match for ‘operator<’ 编译错误。铁律：重载算子的参数和函数体末尾必须双加 const。
比较算子违反“严格弱序”导致运行时段错误（SIGSEGV） 部分选手在重载时，为了让“值相等”的元素优先发生交换，错误地写出了包含等号的判断：return this->value >= other.value;。这直接违反了非自反性（当 $x=y$ 时，$x \ge y$ 且 $y \ge x$ 同时为真）。在 std::priority_queue 内部进行堆化调整时，这种逻辑矛盾会导致堆化算法的边界哨兵失效，指针或下标彻底越界，在评测机上直接返回 Runtime Error (Segmentation Fault)。

经典 NOIP/洛谷真题

1. 洛谷 P4779 【模板】单源最短路径（标准版）

题意描述：给定一个有向图，部分边权为正，求从起点到所有点的最短距离。
问题本质：非负权图上的单源最短路，利用优先队列优化 Dijkstra 算法。
核心解题思路：若直接暴力找当前距离最小的点，复杂度为 $O(V^2)$。此时设计结构体 Node 存储 (当前节点编号, 到起点的距离)，重载比较算子使其按照距离构建 小根堆。每次 $O(\log V)$ 弹出堆顶，更新邻接点后再将新状态 push 进优先队列，将总复杂度完美压制到 $O((V+E) \log V)$。

2. 洛谷 P2949 [USACO09OPEN] 工作调度 Job Scheduling

题意描述：有 $N$ 项工作，每项工作有截止时间 $D_i$ 和利润 $P_i$。完成每项工作都需要 1 个单位时间，求最大总利润。
问题本质：带有时限约束的动态贪心优化。
核心解题思路：首先对所有工作按截止时间从小到大排序。使用一个 小根堆 来维护当前选定的工作利润集合。遍历工作时，若当前工作的截止时间大于堆内元素个数，直接把利润 push 入堆；若截止时间等于堆内元素个数，且当前工作利润大于堆顶（即当前选定集合中的最小利润），则执行 pop 弹出堆顶，再将当前高利润工作 push 入堆。利用优先队列的动态调整，实现低利润任务的实时汰换。