优先队列

#include 
priority_queue

头文件： < queue >

说明：
Type为数据类型，
Container为保存数据的容器，
Functional为元素比较方式。

如果后面两个参数缺省，
容器默认使用vector，比较方式默认使用operator<，
优先队列默认实现大顶堆，队头元素使最大。

（一）实现大顶堆

利用优先队列实现大顶堆。

队列尾部（push） 1, 2, 3, 4, 5, 6 队列头部 （top, pop）

左边是队列尾部，右边是队列头部
从队列尾部到队列头部：从小到大

左边的元素 小于 右边的元素。
小于号，大顶堆。

第一种方式：使用STL的仿函数less

priority_queue,  less>  pque;

第二种方式：自己实现仿函数

struct Less {bool operator() (int a, int b) {return a < b; //小于号，大顶堆}
};
priority_queue , Less>  pque;

第三种方式：缺省第二个、第三个参数

priority_queue  pque;

（二）实现小顶堆

利用优先队列实现小顶堆。

队列尾部（push） 6, 5, 4, 3, 2, 1 队列头部 （top, pop）

左边是队列尾部，右边是队列头部
从队列尾部到队列头部：从大到小

左边的元素 大于 右边的元素。
大于号，小顶堆。

第一种方式：使用STL的仿函数greater

priority_queue,  greater>  pque;

第二种方式：自己实现仿函数

struct Greater {bool operator() (int a, int b) {return a > b; //大于号，小顶堆}
};
priority_queue , Greater>  pque;

常用函数

//判断优先队列是否为空
pque.empty();//从优先队列尾部放入元素
pque.push();//从优先队列头部获取元素
pque.top();//从优先队列头部弹出元素
//弹出元素后，大顶堆自动调整为一个新的大顶堆
//弹出元素后，小顶堆自动调整为一个新的小顶堆
pque.pop();//优先队列的元素大小
pque.size();//优先队列在使用之前要清空
while(!pque.empty()) pque.pop();