Lotplace

本人於該blog的全部文章轉移至[Algorithm] Priority Queue Descending or Ascending Sort – KKWBlog (kkwtech.com)該網域下，其後此處不進行更新，一律於新站點更新。

priority queue常用於有需要資料的排序時使用，有別於queue是以array實作，priority queue則是以heap來達成排序的效果，於c++中提供了已經定義好的類別供我們直接宣告就能使用，基本上跟queue的用法大同小異，因此本篇主要提出如何讓priority queue可以做到生or降冪排序。

降冪排序:
預設的priority queue即為降冪排序，若有需要也可寫成
priority_queue< int, vector<int>, less<int> > pq;

升冪排序:
priority_queue< int, vector<int>, greater<int> > pq;

自定義資料結構排序:
這部分無法使用預先定義好的less or greater使用，需要自己先定義compare才能完成比較。
ex:定義一個Pair <int,int> p，打算以pair.second以升冪排序
備註:關於struct裡的operator()於下一篇文章中再詳細介紹

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

typedef pair<int, int> p;
struct myComp {
    bool operator()(pair<int, int> a,pair<int, int> b) {
        return a.second > b.second;
    }
};

int main()
{
    priority_queue<p, vector<p>, myComp> p1;
    p1.push(make_pair(4, 5));
    p1.push(make_pair(5, 4));
    p1.push(make_pair(1, 6));
    p1.push(make_pair(7, 3));
    p1.push(make_pair(9, 4));

    while (!p1.empty()) {
        cout << p1.top().first
            << " " << p1.top().second
            << endl;
        p1.pop();
    }
    cout << endl;
    return 0;
}

---

Filed under: c++,資結 - @ 2021 年 7 月 23 日 上午 11:20

標籤: c++, data_struct