c++ priority_queue是对其他容器元素顺序的调整包装; 堆的原理

1.定义

priority_queue q;

其中，Type是数据类型，Container是低层容器，如vector, stack, deque等. Functional是比较函数；默认可以使用greater(从小到大）， less(从大到小）排序。例如，定义一个元素为整数的小顶堆：

priority_queue, greater> q;

2.头文件
#include

3.常用接口
push  添加一个元素到队尾，并自动调整堆
pop    弹出队头元素
top   获取队头元素
empty 堆是否为空
size   堆的大小

4.基本数据类型 使用
原始数据[1,2,3,4,5,6,7,8] 
priority_queue q;            //默认是大顶堆
等价于priority_queue, less> q; 

堆内部的数据[8,7,6,5,4,3,2,1]

小顶堆的构造
priority_queue, greater> q2;
堆内部的数据[1,2,3,4,5,6,7,8]

5.关联类型，pair
priority_queue> q3
排序规则默认先比较第一个值，后比较第二个值
pair a(1,2)
pair b(2,3)
pair c(3,4)
q3.push(a);
q3.push(b);
q3.push(c);
q3.top().first, q3.top().second

6.自定义类型，需要重载<运算符
struct tmp1{
    int x;
    tmp1(int a) {x = a;}
    operator <(const tmp1 &a) const {
        return x < a.x;
    }
};

tmp1 t1(3);
tmp1 t2(4);
tmp1 t3(5);

priority_queue q;
//插入元素 
q.push(t1);
q.push(t2);
q.push(t3);

//访问
q.top().x 

#include 
#include
#include
using namespace std;
typedef pair P;//自定义类型
struct tmp1 //运算符重载<
{int x;tmp1(int a) {x = a;}bool operator<(const tmp1& a) const{return x < a.x; //大顶堆}
};struct tmp2 //重写仿函数，用于比较元素
{bool operator() (const pair &a, const pair &b) {if (a.first < b.first) {return true;}return a.second < b.second;}
};int main() {//1.升序队列 , 小顶堆 priority_queue,greater> q1; //2.降序队列, 大顶堆 priority_queue,less> q2; for (int i = 0; i < 10; i++) {q1.push(i);q2.push(i); } while (!q1.empty()) {cout << q1.top() << " ";q1.pop();}cout << endl;while (!q2.empty()) {cout << q2.top() << " ";q2.pop();}cout << endl;//3.关联容器priority_queue
 q3;P p1(1,1);P p2(1,2);P p3(1,3);q3.push(p1);q3.push(p2);q3.push(p3);while (!q3.empty()) {cout << q3.top().first << " - " << q3.top().second << endl;q3.pop();}//3.1 等价于priority_queue,tmp2> q4;q4.push(p1);q4.push(p2);q4.push(p3);while (!q4.empty()) {cout << q4.top().first << " = " << q4.top().second << endl;q4.pop();}//4.自定义类型 priority_queue d;tmp1 a(3);tmp1 b(4);tmp1 c(5);d.push(a);d.push(b);d.push(c);while (!d.empty()) {cout << d.top().x << " ";d.pop();}cout << endl;return 0;
}

参考：c++优先队列(priority_queue)用法详解_吕白_的博客-CSDN博客_c++ 优先队列