struct MyInt {
    MyInt(int _val):val(_val){}
    int val;
};
struct cmp {
    bool operator()(MyInt a, MyInt b) {
        return a.val > b.val; // 这是从小到大排序
    }
};
//bool operator< (MyInt a, MyInt b) {
//    return a.val < b.val; // 这是从大到小排序(相当于默认的大根堆)反之
//}
int main() {
    priority_queue<MyInt, vector<MyInt>, cmp> p;
    p.push(MyInt(1));
    p.push(MyInt(4));
    p.push(MyInt(-4));
    p.push(MyInt(224));
    while (p.size()) {
        cout << p.top().val << " ";
        p.pop();
    }
    cout << endl;
    // priority_queue<int> pInt; // 不做任何修改,默认是从大到小的大根堆
    priority_queue<int,vector<int>,greater<int>> pInt; // 使用greater比较器,就变成小根堆了。
    pInt.push(1);
    pInt.push(4);
    pInt.push(-4);
    pInt.push(224);
    while (pInt.size()) {
        cout << pInt.top() << " "; 
        pInt.pop();
    }
;    system("pause");
}

int main() {
    vector<int> v({ 1,3,4,5,3,2,3,4,5,6,4,3 });
    sort(v.begin(), v.end(), greater<int>()); // 排序默认是从小到大,传入greater后排序方向相反,因此,这里变为从大到小排序。
    for (int n : v) cout << n << " "; 
    system("pause");
}
  • 总结:

    • C++优先队列默认大根,和Java相反。排序默认从小到大,和Java相同
    • 如果传入less<int>,或者重载<或()后,返回使用的是<。则和默认相同:还是小根堆,从小到大</int>
    • 传入greater<int>,或者重载<或()后,返回使用的是>,则变为大根堆,排序从大到小。</int>
  • 居然忘了怎么写优先队列自定义排序了......

    #include <bits/stdc++.h>
    using namespace std;
    // 比较的定义按,首先
    struct cmp {
      // 排序规则为,首先按照第一个元素由小到大排序,如果第一个元素相同,然后按照第二个元素由大到小排序。
      bool operator()(pair<int, int> p1, pair<int, int> p2) {
          if(p1.first > p2.first) {
              return true;
          }
          if(p1.first == p2.first) {
              if(p1.second < p2.second) {
                  return true;
              }
          }
          return false;
      }
    };
    int main() {
      priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
      pq.push({1,2});
      pq.push({1,3});
      pq.push({2,2});
      pq.push({3,3});
      pq.push({4,4});
      pq.push({3,4});
      pq.push({4,2});
      while(pq.size()) {
          pair<int, int> temp = pq.top();
          pq.pop();
          cout << temp.first << " " << temp.second << endl;
      }
    }
  • 自定义排序的时候用上lambda表达式

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main() {
      vector<string> res;
      res.push_back("11223344");
      res.push_back("33221132");
      res.push_back("32423423432423");
      res.push_back("413");
      sort(res.begin(), res.end(),[](string a, string b) {
          if(a.size()!=b.size()) {
              return a.size() < b.size();//按长度降序
          }
          return a<b;//长度一样,按字典序降序。
      });
      for(int i=0; i<res.size(); i++) {
          cout << res[i] << endl;
      }
      return 0;
    }