Priority_queue的less是升序还是降序

蔚落 2024-04-01 18:42 172阅读 0赞

#### 一、问题 ####

sort一个数组，less函数明明是升序，怎么到优先队列这里就是降序了？

打印vector

vector<int>  nums = { 9,6,4,8,7,2 };
        sort(nums.begin(), nums.end(), less<int>()); // 升序排列
    
        for (auto item : nums)
        {
            cout << item << "  ";
        }

![11f613eb47b84c768bb1c1e633ba1876.png][]

打印 priority\_queue

vector<int> nums = { 9,6,4,8,7,2 };
        priority_queue <int, vector<int>, less<int>> pq; // 降序排列
    
        for (auto item : nums)
        {
            pq.push(item);
    
        }
        while (!pq.empty())
        {
            cout << pq.top() << ' ';
            pq.pop();
        }

![1c99f213c1c24c01afbaf6a7e127d754.png][]

#### 二、**greater和less的实现** ####

先来看看实现

greater定义如下

template <class T> struct greater{
         bool operate() (const T& x, const T &y) const{return x>y;}
         typedef T first_argument_type;
         typedef T second_argument_type;
         typedef bool result_type;
     }

less定义如下

template <class T> struct less {
         bool operator() (const T& x, const T& y) const {return x<y;}
         typedef T first_argument_type;
         typedef T second_argument_type;
         typedef bool result_type;
     };

主要原因是因为priority\_queue的内部实现方法是堆，堆的内部实现是vector，每次出堆的时候 实际上是**堆顶元素和最后一个元素互换(把最大元素沉到数组末端)**。假如没有出堆这一个过程，而是继续将数据缓存在vector中，最后形成的数组就是升序的。只是**由于出堆这一过程，导致了元素出堆反序了**，相当于逆序输出。

#### 三、实践 ####

[1094. 拼车][1094.]

下面是自定义的优先队列使用，很有参考性

class Solution {
    public:
        bool carPooling(vector<vector<int>> &trips, int capacity)
        {
            // 1. sort by start_location
            sort(trips.begin(), trips.end(), [](vector<int> &a, vector<int> &b) { return a[1] < b[1]; });
            // 2. priority_queue
            auto cmp = [](vector<int> &a, vector<int> &b) { return a[2] > b[2]; };
            // min heap
            priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> que(cmp);
            int cnt = 0;  // people cnt
            for (int i = 0; i < trips.size(); ++i) {
                // 下车
                while (!que.empty() && trips[i][1] >= que.top()[2]) {  // 下车
                    cnt -= que.top()[0];                               // people cnt
                    que.pop();
                }
                // 上车
                cnt += trips[i][0];
                if (cnt > capacity) {
                    return false;
                }
                que.push(trips[i]);
            }
            return true;
        }
    };

参考：

[优先级队列全解！还分不清less是升序还是降序就快来看看把 - 知乎][less_ -]

[11f613eb47b84c768bb1c1e633ba1876.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/241eec16c1ed40a6a8be28b55a8b62b3.png
[1c99f213c1c24c01afbaf6a7e127d754.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0bfb9a3900f44d59a976c99fa1c17352.png
[1094.]: https://leetcode.cn/problems/car-pooling/
[less_ -]: https://zhuanlan.zhihu.com/p/355974733