C/C++优先队列std::priority_queue实现大顶堆和小顶堆_c++priority_queue中的小顶堆

优先队列

#include <queue>
priority_queue<Type, Container, Functional>
1
2

头文件： < queue >

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

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

（一）实现大顶堆

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

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

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

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

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

priority_queue<int,  vector<int>,  less<int>>  pque;
1

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

struct Less {
    bool operator() (int a, int b) {
        return a < b; //小于号，大顶堆
    }
};
priority_queue <int, vector<int>, Less>  pque;
1
2
3
4
5
6

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

priority_queue<int>  pque;
1

（二）实现小顶堆

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

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

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

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

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

priority_queue<int,  vector<int>,  greater<int>>  pque;
1

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

struct Greater {
    bool operator() (int a, int b) {
        return a > b; //大于号，小顶堆
    }
};
priority_queue <int, vector<int>, Greater>  pque;
1
2
3
4
5
6

常用函数

//判断优先队列是否为空
pque.empty();

//从优先队列尾部放入元素
pque.push();

//从优先队列头部获取元素
pque.top();

//从优先队列头部弹出元素
//弹出元素后，大顶堆自动调整为一个新的大顶堆
//弹出元素后，小顶堆自动调整为一个新的小顶堆
pque.pop();

//优先队列的元素大小
pque.size();

//优先队列在使用之前要清空
while(!pque.empty()) pque.pop();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19