Priority Queue中Comparator函数返回值对元素排序的疑问

Let's work through your questions about how the comparator affects element ordering in priority_queue, using your code and output as a guide.

First, here's your code for reference:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Compfunc {
    bool operator() (const int &a, const int &b) {
        //cout << "a: " << a << " vs b: " << b << endl;
        return (a < b);
    }
};

void callPQ(vector<int> &vec) {
    priority_queue<int, vector<int>, Compfunc> pq;
    for (auto num : vec) {
        cout << "Pushing : " << num << endl;
        pq.push(num);
    }
    cout << "Printing:" << endl;
    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }
}

int main() {
    vector<int> vec{5, 6, 4, 9, 2, 0};
    callPQ(vec);
    return 0;
}

And the output you got:

Pushing : 5
Pushing : 6
Pushing : 4
Pushing : 9
Pushing : 2
Pushing : 0
Printing:
9
6
5
4
2
0

Let's start with the core rule that's key to resolving your confusion:

For priority_queue, the comparator comp(a, b) returns true if a should come before b in the strict weak ordering we define. However, the queue's top() element is always the one that sits at the end of this ordering (the highest-priority element).

Question 1: Is the newly pushed element always b in Compfunc? #

Nope, that's not a fixed rule. When you push a new element, the underlying heap structure does an "up-heap" operation to keep the heap valid. During this process, the new element is compared with its parent nodes in the heap, and it can act as either a or b depending on which direction the comparison is happening.

For example:

• When you push 6 after 5, the heap compares the existing root (5) with the new element (6), so the comparator runs as comp(5, 6) (here, a=5, b=6).
• If you later push 2, it gets added to the bottom of the heap. If its parent is 4, the comparator would run as comp(2, 4) (a=2, b=4).
• If you pushed a very large element that needs to bubble up multiple levels (like 9 in your code), it might be compared against 6 first—here, the comparator would be comp(6,9) (a=6, b=9).

The takeaway: the new element isn't always b—it depends on how the heap is rearranging itself to maintain its property.

Question 2: Why does 6 become the top when comp(5,6) returns true (saying 5 should come before 6)? #

This is the most common sticking point with priority_queue comparators, so let's break it down clearly:

The comparator's "comes before" refers to the logical ordering sequence, not the heap's top-to-bottom order.

Your Compfunc uses return a < b, which defines a sequence where smaller numbers come before larger ones: 0 → 2 → 4 →5 →6 →9. Now, priority_queue is built to give you the element that's last in this sequence (the highest priority) as the top element.

So when comp(5,6) returns true, it means "5 should be placed before 6 in our logical order". Since 6 is later in that sequence, it has higher priority—and thus moves to the top of the heap.

Another way to think about it: the comparator tells the queue, "should a be placed lower than b in the heap?" If comp(a,b) is true, a is lower priority, so b gets placed above a (closer to the top).

If you wanted a min-heap (smallest element at the top), you'd reverse the comparator to return a > b. That would create a logical order where larger numbers come before smaller ones, so the smallest element (last in the sequence) would be the top.

Quick Confirmation #

Your comparator is actually identical to the default less<int> that priority_queue uses if you don't specify one. That's why your code produces a max-heap, with the largest elements coming out first.

内容的提问来源于stack exchange，提问作者adizone