std::greater在std::priority_queue中的行为及与std::sort的差异疑问

这个问题确实容易搞混，因为std::sort和std::priority_queue对比较函数的语义定义完全不一样，咱们一步步拆解清楚：

在std::sort中，比较函数的作用非常直接：判断第一个参数是否应该排在第二个参数的前面。
当你写std::sort(arr, arr+len, std::greater<int>())时，std::greater<int>()会返回a > b的布尔值——也就是说，如果a比b大，a就会被放在b的前面，最终数组自然呈现从大到小的非递增顺序。

而std::priority_queue的比较函数，语义完全不同：它是用来定义**“哪个元素的优先级更低”，或者说，判断一个元素是否应该被“压在另一个元素下面”**。

默认情况下，std::priority_queue用的是std::less<int>，这时候的规则是：如果a < b，说明a的优先级比b低，所以b会被放在堆的更上层（成为堆顶的候选），最终堆顶是整个队列里最大的元素——这就是我们常说的“大顶堆”。

当你换成std::greater<int>时，规则直接反转：如果a > b，说明a的优先级比b低，所以b会被调到更上层。这时候整个堆的结构变成了小顶堆：堆顶是队列里最小的元素，因为所有比它大的元素都会被判定为“优先级更低”，被压在堆的下层。

举个直观的例子：
如果往std::priority_queue<int, std::vector<int>, std::greater<int>>里插入5、3、7这三个数：

• 插入5，堆里只有5，堆顶是5；
• 插入3，比较greater<int>()(5,3)（即判断5>3），结果为true，说明5优先级比3低，所以3被调到堆顶，现在堆顶是3；
• 插入7，先比较greater<int>()(3,7)（3>7为false），说明3优先级更高不用动；再比较greater<int>()(5,7)（5>7为false），5优先级也比7高，所以7放在最底层。最终堆顶还是3，也就是最小的元素。

• std::sort的比较函数：决定元素的前后排列顺序（comp(a,b)为true → a排在b前面）
• std::priority_queue的比较函数：决定元素的优先级高低（comp(a,b)为true → a优先级比b低，b会在堆的更上层）

这样就能明白为什么同样用std::greater<int>，一个是降序排序，一个会返回最小元素了。

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