C++中priority_queue优先队列

海盗船长

发布于 2020-08-27 17:46:17

5380

发布于 2020-08-27 17:46:17

优先队列的概念

优先队列包含在头文件中。优先队列是由二项队列编写而成的，可以以log（n）的效率查找一个队列中最大值或最小值（最大值和最小值是由你选择创建的优先队列的性质决定的），这在很多场合可以派上很大的用处，例如prim算法如果结合优先队列可以产生出很好的效果。 priority_queue的模板生命是带有三个参数的：

priority_queue<type,container,function>；
//type是数据的类型
//container为实现优先队列的底层容器
//function为元素间的比较方式

【注意】container要求必须是数组形式实现的容器，如vector，deque，而不能是list。在c++标准库中，默认情况下是以vector为容器，以operator<为比较方式，所以在只使用第一个参数时，优先队列默认是一个最大堆，每次输出的堆顶元素是此时堆中的最大元素。

优先队列的操作

函数方法	功能介绍
empty	测试容器是否为空
size	测试容器大小
top	访问顶层元素
push	插入元素
emplace	构造并插入元素
pop	删除顶部元素
swap	交换内容

优先队列的实例

#include<queue>
#include<functional>

int main()
{
	priority_queue<int, vector<int>, greater<int> > myQueue;   //构造一个空的优先队列,此优先队列是一个小顶堆
	uniform_int_distribution<unsigned> u(0, 100);    //用于在0到100之间生成均匀分布的随机数
	default_random_engine e;     //定义一个随机数引擎
	int value;
	for (int i = 0; i<10; i++)
	{
		value = u(e);
		cout << value << " ";
		myQueue.push(value);    //将生成的随机数放入到队列中
	}
	cout << endl;
	while (!myQueue.empty())    //此循环将会按照升序输出优先队列中的元素
	{
		cout << myQueue.top() << " ";    //输出队列中最小的元素
		myQueue.pop();
	}
	cout << endl;
	return 0;
}

#include<iostream>
#include<random>
using namespace std;
#include<queue>

class node
{
public:
	node(int x = 0, int y = 0) :m_x(x), m_y(y){}
	friend bool operator<(const node &n1, const node &n2)    //重载<运算符是用于大顶堆
	{
		return n1.m_x<n2.m_x;
	}
	friend bool operator>(const node &n1, const node &n2)    //重载>运算符是用于小顶堆
	{
		return n1.m_x>n2.m_x;
	}
	friend ostream &operator<<(ostream &out, const node &n)
	{
		cout << "(" << n.m_x << "," << n.m_y << ")";
		return out;
	}
private:
	int m_x, m_y;
};
int main()
{
	priority_queue<node, vector<node>, greater<node> > myQueue;
	uniform_int_distribution<unsigned> u(0, 100);
	default_random_engine e;
	int value1, value2;
	for (int i = 0; i<10; i++)
	{
		value1 = u(e);
		value2 = u(e);
		cout << "(" << value1 << "," << value2 << ")";
		myQueue.push(node(value1, value2));
	}
	cout << endl;
	while (!myQueue.empty())
	{
		cout << myQueue.top() << " ";
		myQueue.pop();
	}
	cout << endl;
	system("pause");
	return 0;
}

在c++中，可以像对待其他运算符一样对待函数调用运算符()；这个运算符也可以重载。()运算符能够返回任何类型，可以使用任何数量的参数，但和赋值运算符一样，该运算符只能重载为成员函数。包含函数调用运算符定义的对象称为函数对象。函数对象也是对象，只是它们的行为表现得像函数而已。当调用函数对象时，其参数是函数调用运算符的参数。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/05/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

容器