In-Depth Understanding of C++ Priority Queues and Comparator Design

Core Logic and Mathematical Principles

std::priority_queue is a container adapter in the C++ Standard Template Library (STL), which is implemented as a binary heap structure based on std::vector by default. The dynamic adjustment of max-heaps and min-heaps strictly depends on the Total Ordering relation among elements.

Mathematically, the standard library requires that custom comparison operators must satisfy Strict Weak Ordering. Let the comparison operator be $\prec$, and any elements $x, y, z$ in the set must satisfy the following three axioms:

Irreflexivity: $x \prec x$ is always false.
Asymmetry: If $x \prec y$ is true, then $y \prec x$ must be false.
Transitivity: If $x \prec y$ and $y \prec z$ are true, then $x \prec z$ must be true.

In the internal logic of std::priority_queue, std::less<T> is used by default to determine the priority of elements.

When the underlying heap is heapified upwards or downwards, if Compare(new_node, parent_node) returns true, no swap occurs between the two nodes.
Counterintuitive Positioning Rule: The underlying determination of a max-heap is "swap if the parent node is less than the child node". Therefore, when we overload the comparison operator and return true when $x < y$, the priority queue behaves as a max-heap; conversely, if we return true when $x > y$, the priority queue reverses to a min-heap.

State Design and Algorithm Derivation

In NOIP practical scenarios, it is often necessary to maintain composite states with multiple attributes (for example: (current point, current shortest distance) in graph theory, or (deadline, value) in greedy problems).

1. Structure State Design

Define the composite state structure Node:

struct Node {
    int id;
    int value;
    // Multi-dimensional state extension
};

2. Comparison Operator Overloading Derivation

To achieve double-key sorting (the primary key value in ascending order, and the secondary key id in ascending order, i.e., building a min-heap), the logic for the comparison operator is derived as follows:

If the primary key value is not equal, then the one with the smaller value has higher priority. Since we need to build a min-heap, we need to reverse the total ordering symbol: return true when this->value > other.value.
If the primary key value is equal, then compare the secondary key id. Similarly, return true when this->id > other.id.

The mathematical expression can be expressed as:

$$\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++ Standard Source Code

Below is a custom structure priority queue template compiled strictly in a Linux environment using g++ -O2, commonly used in high-frequency scenarios such as Dijkstra's algorithm in graph theory.

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

struct Node {
    int id;
    int dis;

    // Constructor explicitly initializes
    Node(int _id, int _dis) : id(_id), dis(_dis) {}

    // Method 1: Overload the < operator within the structure
    // Fatal pitfall: parameters must be const qualified, and the function body must end with const, otherwise STL internal calls will cause compilation errors
    bool operator<(const Node& other) const {
        if (this->dis != other.dis) {
            // Counterintuitive: writing > here means the smaller dis has higher priority, thus constructing a min-heap
            return this->dis > other.dis; 
        }
        return this->id > other.id;
    }
};

// Method 2: Define an independent functor (structure comparison operator) for specific priority_queue declarations
struct CustomCompare {
    bool operator()(const Node& a, const Node& b) const {
        if (a.dis != b.dis) {
            return a.dis > b.dis; // Min-heap logic
        }
        return a.id > b.id;
    }
};

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

    // Using method 1: defaults to using the overloaded < operator (note: STL internally defaults to less, using < for internal judgment, reversed to implement min-heap)
    std::priority_queue<Node> pq_default;

    // Using method 2: explicitly pass the underlying container and custom functor
    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 Practical Pitfall Guide

Operator overloading without const qualifier leading to compilation failure When overloading operator<, writing it as bool operator<(Node& other). Since std::priority_queue internally passes in constant references of type const Node& for safety, when the standard library attempts to compare two constant objects using <, g++ will throw hundreds of lines of no match for ‘operator<’ compilation errors due to the absence of a corresponding const member function. Rule of thumb: both the parameters of overloaded operators and the end of the function body must have const added.
Comparison operator violating "Strict Weak Ordering" causing runtime segmentation fault (SIGSEGV) Some contestants, in order to prioritize the exchange of elements with "equal values", mistakenly wrote a comparison including equality: return this->value >= other.value;. This directly violates irreflexivity (when $x=y$, both $x \ge y$ and $y \ge x$ are true). During heapification adjustments in std::priority_queue, this logical contradiction leads to the failure of boundary sentinels in the heapification algorithm, causing pointers or indices to go out of bounds, resulting in a direct return of Runtime Error (Segmentation Fault) on the judging machine.

Classic NOIP/Luogu Problems

1. Luogu P4779 [Template] Single Source Shortest Path (Standard Version)

Problem Description: Given a directed graph with some edges having positive weights, find the shortest distance from the starting point to all points.
Core Problem Essence: Single-source shortest path on non-negative weight graphs, optimizing Dijkstra's algorithm using priority queues.
Core Solution Idea: If we directly look for the point with the current minimum distance, the complexity is $O(V^2)$. At this point, we design the structure Node to store (current node number, distance to the starting point), and overload the comparison operator to construct a min-heap based on distance. Each time we pop the top with a complexity of $O(\log V)$, update adjacent points, and then push the new state into the priority queue, perfectly compressing the total complexity to $O((V+E) \log V)$.

2. Luogu P2949 [USACO09OPEN] Job Scheduling

Problem Description: There are $N$ jobs, each with a deadline $D_i$ and profit $P_i$. Each job requires 1 unit of time to complete, and we need to find the maximum total profit.
Core Problem Essence: Dynamic greedy optimization with deadline constraints.
Core Solution Idea: First, sort all jobs in ascending order of deadlines. Use a min-heap to maintain the current selected job profit set. When traversing jobs, if the current job's deadline is greater than the number of elements in the heap, directly push the profit into the heap; if the deadline equals the number of elements in the heap, and the current job profit is greater than the top of the heap (i.e., the minimum profit in the currently selected set), pop the top and push the current high-profit job into the heap. Utilize the dynamic adjustment of the priority queue to achieve real-time replacement of low-profit tasks.