一、priority_queue  优先队列本质就是 堆

堆： 完全二叉树，任意结点比其孩子结点小->小根堆, 任意结点比其孩子结点大->大根堆,

头文件包含：#include 

二、优先级队列的模板参数列表：

template ,  class Compare = less > class priority_queue;

第二个参数指的是采用什么底层容器进行存储，默认使用vector，因为优先级队列的底层结构就是堆，而堆是一种完全二叉树，完全二叉树就适应这种顺序存储的结构

第三个参数给出的是什么样的比较方式默认采用less方式进行比较从而生成大堆，如果想要使其生成小堆，在模板参数中给出greater。        如果要使用greater 则需要包含头文件#include

三、基本接口的使用

①构造一个空的优先队列 进行插入

void Testpriority_queue01()
{priority_queue  q;q.push(1);q.push(2);q.push(632);q.push(34);q.push(23);q.push(6);q.push(67);q.push(95);q.push(23);cout << q.size() << endl;cout << q.top() << endl;q.pop();q.pop();q.pop();q.pop();cout << q.size() << endl;cout << q.top() << endl;
}

② 利用迭代器来进行区间构造

    使用greater 第一种做法是错误的，没有考虑到第二个参数。

void Testpriority_queue03()
{// priority_queue > q; 错误priority_queue , greater> q;q.push(1);q.push(2);q.push(632);q.push(34);q.push(23);q.push(6);q.push(67);q.push(95);q.push(23);cout << q.size() << endl;cout << q.top() << endl;q.pop();q.pop();q.pop();q.pop();cout << q.size() << endl;cout << q.top() << endl;
}

④ 关于自定义类型数据的插入

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}private:int _year;int _month;int _day;
};void Testpriority_queue04()
{priority_queue q;Date d1(2023, 1, 12);Date d2(2023, 1, 13);Date d3(2023, 1, 11);q.push(d1);q.push(d2);q.push(d3);cout << q.size() << endl;
}

 发生报错，优先队列默认采用less的比较方式来生成一个大堆，可是在这里插入自定义类型Date时，发生了报错，原因显而易见，编译器无法知道数据比较是用Date中的三个参数的哪一个来进行比较。

四、自定义类型数据插入优先级队列发生报错的解决方式

如果编译器无法知道我们的比较方式是如何进行的，那么我们就得告诉编译器如何进行比较

① 【方式一】在Date类中重载比较方式

这种方式易于理解，你不知道怎么比，那我就在Date类中告诉你怎么比较，该用谁来与谁来进行比较。

    bool operator<(const Date& d)const{return _day < d._day;}bool operator>(const Date& d)const{return _day > d._day;}

 ② 【方式二】使用函数指针

那么我写一个函数Compare来给编译器传递我进行比较的方式，传参时将Compare放入q之后的（）内，即为q(Compare)；

但是这样还不够，如果想要使用函数指针作为函数参数，那么必须把函数类型在优先级队列的模板参数列表中给出来。

优先级队列的模板参数列表上面也提到过，第一个参数为存放元素的类型（Date），第二个参数为什么样的容器来存储（vector），第三个参数就需要传入函数指针的类型

如下为函数指针取别名方式：

typedef bool (*PCOM)(const Date& left, const Date& right);  PCOM为该函数指针的别名

如下为定义优先级队列q：

priority_queue, PCOM> q(Compare);

typedef bool (*PCOM)(const Date& left, const Date& right);
bool Compare(const Date& left, const Date& right)
{return left.GetDay() < right.GetDay();
}void Testpriority_queue05()
{priority_queue, PCOM> q(Compare);Date d1(2023, 1, 12);Date d2(2023, 1, 13);Date d3(2023, 1, 11);q.push(d1);q.push(d2);q.push(d3);cout << q.size() << endl;
}

③【方式三】使用仿函数

所谓的仿函数，就是对（）进行运算符重载。使之成为一个能表示函数功能的函数。

为什么是Com？  因为优先级队列的第三个参数为一个class类型，所以需要新实现一个类，类中仅需重载（）

 如下在Com类中写入一个（）运算符重载函数，说明了Date类内的比较方式，接着在优先级队列进行定义的时候将Com作为模板参数传入即可。

class Com
{
public:bool operator()(const Date& left, const Date& right)const{return left.GetDay() < right.GetDay();}
};void Testpriority_queue06()
{priority_queue, Com> q;Date d1(2023, 1, 12);Date d2(2023, 1, 13);Date d3(2023, 1, 11);q.push(d1);q.push(d2);q.push(d3);cout << q.size() << endl;
}

五、对于优先级队列存放指针的探讨

 如上图，优先级队列中存储元素类型模板参数为Date*，即存储的是Date类型的指针，在默认的优先级队列中，比较方式是按照less的方式进行比较，而指针的本质就是一块地址，这个地址本质就是一串整形十六进制数据，这个数据也能依据less的比较方式来在优先级队列中存储，即该队列就是按照地址的高低大小来进行建堆，地址高即数值大就排在靠近堆顶位置。

可是我的本意是用我指针所指向的内容来进行比较，这里却使用了指针的地址来进行比较，显然没有任何意义，那么如何实现我最初的目的呢？

仿函数的使用：

        提供一个ComPtr的指针比较方式的类，类中传入left，right俩个Date类型的指针，利用这俩个指针来调用Date类中的GetDay()函数来告诉编译器所需要比较的内容具体是什么。

class ComPtr
{
public:bool operator()(const Date* left, const Date* right)const{return left->GetDay() < right->GetDay();}
};
void Testpriority_queue07()
{// 优先级队列中存放的是指针priority_queue, ComPtr> q;Date d1(2023, 1, 12);Date d2(2023, 1, 13);Date d3(2023, 1, 11);q.push(&d1);q.push(&d2);q.push(&d3);
}

 按照指针的内容大小来进行建堆：