---
tags: STL
title: Priority Queue
---

:::success
# 優先佇列 Priority Queue

## 實現

- std::priority_queue背後是heap

## 用途

- 為一序列容器
- 是一個帶優先級的queue
- 可以==很快很方便的==加入元素或取出當前最優先的元素

## 用法

### 宣告

- 需要引入函式庫\<queue>

#include <queue>
//priority_queue<"dataType", "container", "comparisonFunction"> "name";
//container默認為vector，comparisonFunction默認為由大到小排序

priority_queue<int> test;
priority_queue<int, vector<int>, greater<int> > pq; //由小到大

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second;
} //priority_queue優先判定為!cmp，所以這個cmp會使pq中小的優先
priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq;

### 函式

狀態回傳
priority_queue.empty(); //回傳priority_queue是否為空
priority_queue.size(); //回傳priority_queue目前元素數

加入移除元素
priority_queue.push(e); //將e加入priority_queue
priority_queue.pop(); //移除priority_queue中的第一個元素

操作元素
priority_queue.top(); //呼叫priority_queue中的第一個元素

- 插入和移除的複雜度為 $O(logN)$，初始化的複雜度為$O(logN)$(建立heap，若建立後再一個一個push則為$O(NlogN)$)
- 呼叫元素的複雜度為$O(1)$
:::