# 【程式】C++ STL用法 `priority_queue` 自定義型別、比較函式

## 前言
以前用`priority_queue`都只知道基本用法，做了[378. Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/)這題leetcode題目後，才發現原來不只基本用法，還可以放入自定義型別，進而幫他做排序。

---

## Syntax

struct node{
    int x, y, val;
    node (int a, int b, int c):
        x(a), y(b), val(c) {}
};

struct cmp{
    bool operator() ( node a, node b ){      
        return a.val > b.val; // 由小排到大
    }
    // return 1 代表要交換
    // return 0 代表不用交換
};

priority_queue<node, vector<node>, cmp> pq;

---

## 範例

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

struct node{
    int x, y, val;
    node (int a, int b, int c):
        x(a), y(b), val(c) {}
};

struct cmp{
    bool operator() ( node a, node b ){      
        return a.val > b.val; // 由小排到大
    }
    // return 1 代表要交換
    // return 0 代表不用交換
};

int main(){
    priority_queue<node, vector<node>, cmp> pq;    
    for (int i=10;i>0;i++){
        node temp(0,0,i);
        pq.push(temp);
    }
    while(!pq.empty()){
        node t = pq.top();
        cout << t.a << " " << t.b << " " << t.val << endl;
        pq.pop();
    }
    return 0;
}

輸出output:
> 0 0 1
> 0 0 2
> 0 0 3
> 0 0 4
> 0 0 5
> 0 0 6
> 0 0 7
> 0 0 8
> 0 0 9
> 0 0 10

---

## 統整

- ```pq.push(var)``` 把值放進queue裡面，會自動排序
- ```pq.pop()``` 把最大的值從queue中刪除
- ```pq.top()``` 回傳最大值
- ```pq.size()``` 回傳有多少東西在queue裡面
- ```pq.empty()``` 回傳1或0，1代表沒東西，0代表還有東西
- 自定義型別 和 比較函式

struct node{
int x, y, val;
node (int a, int b, int c):
x(a), y(b), val(c) {}
};

struct cmp{
bool operator() ( node a, node b ){
return a.val > b.val; // 由小排到大
}

};
priority_queue<node, vector<node>, cmp> pq;

---

## 參考
1. [CSDN C++ priority_queue的自定义比较方式](https://blog.csdn.net/AAMahone/article/details/82787184)
2. [自己的筆記](https://hackmd.io/bENvmyTjQ4O8z9a_0UMo5g?edit)
###### tags: `程式` `學習` `筆記`