---
title: "priority_queue"
created: 2025-11-28
tags:
  - 算法
---

# priority_queue

优先级队列`priority_queue`

优先级队列是一个拥有权值的gueue，其内部元素按照元素的权值排列。权值较高者排在最前优先出队。其中缺省情况下系统是通过一个max-heap以堆实现完成排序特性，表现为一个以vector表现的完全二叉树。

## 介绍

它是一个queue，所以只允许在底端加入元素，并从顶端取出元素。

但是优先级队列中的元素并非依照被推入队列的顺序排列。而是自动依照元素的权值排列。权值最高者排在最前面。

缺省的情况下维护的是一个大堆，即权值以从高到低排列。

![[image-815d2f86.png]]

### 参数

`priority_queue<Type, Container, Functional>`

其中Type代表数据类型

Container代表容器类型，缺省状态为vector

Functional是比较方式，默认采用的是大顶堆(less<>)。

```cpp
//升序队列 小顶堆 great小到大
priority_queue <int,vector<int>,greater<int>> minheap;

//降序队列 大顶堆 Less大到小 默认
priority_queue<int,vector<int>,less<int>> maxheap;
priority_queue<int> maxheap;
```

### api

```
q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q·push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top()：//返回q的第一个元素
```

## 使用技巧

使用优先队列时往往不局限于int 对于复杂的数据结构 该怎么让他保持大小根的特性呢

### 重载<

它也是默认用 `operator<` 表示大根堆的 要改成小根堆或者设置什么多关键字排序也是一样的原理 要么把<重载成>或自己想要的比较规则

```cpp
#include<bits/stdc++.h>
using namespace std;

struct node1{
    int x,y;
    bool operator<(const node1& other)const{
        return x<other.x;
    }
};
priority_queue<node1> maxheap;

struct node2{
    int x,y;
    bool operator<(const node2& other)const{
        return x>other.x;
    }
};
priority_queue<node2> minheap;

int main()
{
    node1 a1={1,2};node1 b1={0,2};node1 c1={1,3};node1 d1={2,5};
    maxheap.push(a1);maxheap.push(b1);maxheap.push(c1);maxheap.push(d1);
    while(!maxheap.empty()){
        cout<<maxheap.top().x<<","<<maxheap.top().y<<endl;
        maxheap.pop();
    }

    cout<<endl;

    node2 a2={1,2};node2 b2={0,2};node2 c2={1,3};node2 d2={2,5};
    minheap.push(a2);minheap.push(b2);minheap.push(c2);minheap.push(d2);
    while(!minheap.empty()){
        cout<<minheap.top().x<<","<<minheap.top().y<<endl;
        minheap.pop();
    }

    return 0;
}
```

![[image-e8b1471b.png]]

### 仿函数

要么就直接重写一个比较规则 传入参数里告诉它让它使用

```cpp
#include<bits/stdc++.h>
using namespace std;

struct Person {
    string name;
    int age;
    Person(string n, int a) : name(n), age(a) {}
};

struct CompareAge_max {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age; // 较大的年龄优先
    }
};

struct CompareAge_min {
    bool operator()(const Person& a, const Person& b) {
        return a.age > b.age; // 较大的年龄优先
    }
};

priority_queue<Person, vector<Person>, CompareAge_max> people_maxheap;
priority_queue<Person, vector<Person>, CompareAge_min> people_minheap;

int main()
{
    Person a={"张三",17}; Person b={"李四",19}; Person c={"王五",12};

    people_maxheap.push(a);people_maxheap.push(b);people_maxheap.push(c);
    while(!people_maxheap.empty()){
        cout<<people_maxheap.top().name<<","<<people_maxheap.top().age<<endl;
        people_maxheap.pop();
    }

    puts(" ");

    people_minheap.push(a);people_minheap.push(b);people_minheap.push(c);
    while(!people_minheap.empty()){
        cout<<people_minheap.top().name<<","<<people_minheap.top().age<<endl;
        people_minheap.pop();
    }

    return 0;
}
```

![[image-f0902954.png]]

或者这样

```java
#include<bits/stdc++.h>
using namespace std;

template <typename T>
class cmp_max{
    public:
        bool operator()(T a,T b)
        {
            return a.age<b.age;
        }
};

template <typename T>
class cmp_min{
    public:
        bool operator()(T a,T b)
        {
            return a.age>b.age;
        }
};

struct Person {
    string name;
    int age;
    Person(string n, int a) : name(n), age(a) {}
};

priority_queue<Person, vector<Person>, cmp_max<Person>> people_maxheap;
priority_queue<Person, vector<Person>, cmp_min<Person>> people_minheap;

int main()
{
    Person a={"张三",17}; Person b={"李四",19}; Person c={"王五",12};

    people_maxheap.push(a);people_maxheap.push(b);people_maxheap.push(c);
    while(!people_maxheap.empty()){
        cout<<people_maxheap.top().name<<","<<people_maxheap.top().age<<endl;
        people_maxheap.pop();
    }

    puts(" ");

    people_minheap.push(a);people_minheap.push(b);people_minheap.push(c);
    while(!people_minheap.empty()){
        cout<<people_minheap.top().name<<","<<people_minheap.top().age<<endl;
        people_minheap.pop();
    }

    return 0;
}
```

![[image-e4b7dd64.png]]

此外还有lambda表达式和函数指针的写法

越往下越不推荐 还是在node里面重载<最方便 灵活性高的话就直接写个仿函数（其一）

## 小结

反正可以观察到一个东西 就是<对应的就是大根堆 >对应的是小根堆

这与sort居然是相反的（sort <升序 >降序）

理解成对头在右侧就没问题了

优先级队列排序函数的顺序问题

对于sort和priority\_queue，使用greater和less类模板是结果不同的。

主要原因是因为priority_queue的内部实现方法是堆，less对应的是大顶堆。在此排序下调用top()得到的是堆顶，也就是取值时是从大到小。push对应的底层函数是push\*heap()，每次添加元素入堆时，在默认情况下添加进去的数据作为较小值入堆。

```cpp
//默认都是Less
sort(vec.begin(),vec.end(),less<int>());//内置类型从小到大升序
priority_queue <int,vector<int>,less<int> > pql;//top出数据从大到小降序
sort(vec.begin(),vec.end(),greater<int>());//内置类型从大到小降序
priority_queue<int,vector<int>,greater<int>>pqg;//top出数据从小到大升序
```

![[image-9a6dd3a4.png]]

除了priority\_queue使用的是堆，导致全部大小比较反了过来，其他均是正常符合逻辑的操作，即判断为func(a,b)判断为true则a在前。

只有priority\_queue特殊，如果func(a,b)判断为true，优先级队列中b在前

注意：队头在最右侧

```cpp
struct node{
    int x,y;
}point;
bool operator<(const node &a,const node &b)
{
    if(a.x==b.x)
        return a.y>b.y;
    else
        return a.x<b.x;
}
priority_queue<node> Q;
```

1、Sort排序里面的比较函数，将元素按照比较函数的逻辑排序

2、优先队列priority\_queue里面默认使用大顶堆，也就是less<>，并不是按照比较的顺序直接进行排序。

3、如上述代码，对于a和b的排序，先对a.x和b.x进行比较，如果前者小，其优先级低，放在后面，按照降序排列；如果两者相等，再对a.y和b.y进行比较，如果前者小，此时优先级高，放在前面，按照升序排列。

4、总结，先按照x降序排列，对于x相同的，按照y升序排列，而非直接根据大小进行排列。排列的标准是优先级，而非具体的数值大小。返回true代表优先级更低。

---
⬅️ [[运算符重载 排序|运算符重载 排序]] 🏠 [[00-刷题理模型]] ➡️ [[堆用法与模型|堆用法与模型]]