位置：首页-资讯-后端开发

C++深入刨析优先级队列priority_queue的使用

2022-11-13 14:08

短信预约 -IT技能 免费直播动态提醒

一、priority_queue的介绍

priority_queue官方文档介绍

翻译：

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为优先级队列的底层容器类，priority_queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部"弹出，其称为优先队列的顶部。
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作:

empty()：检测容器是否为空。

size()：返回容器中有效元素个数。

front()：返回容器中第一个元素的引用。

push_back()：在容器尾部插入元素。

pop_back()：删除容器尾部元素。

标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

二、priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法（堆的创建与应用）将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。

⭐️⭐️⭐️：常用的函数接口

priority_queue()/priority_queue(first,last),构造优先级队列。
empty()，检测优先级队列是否为空，若是返回True。
top()，返回优先级队列中最大（最小）元素，即堆顶元素。
push()，在优先级队列中插入元素。
pop()，删除优先级队列中最大（最小）元素，即堆顶元素。

下面我们就举一个例子:

存放自定义类型，这样更具代表性！

template<class T>
class greater
{
public:
	bool operator()(const T& p1, const T& p2) const
	{
		return p1 > p2;
	}
};
struct person
{
	person(string name = "", int age = -1)
		:_name(name)
		, _age(age)
	{}
	bool operator<(const person& p) const
	{
		return _age < p._age;
	}
	bool operator>(const person& p) const
	{
		return _age > p._age;
	}
	string _name;
	int _age;
};
ostream& operator<<(ostream& out, const person& p)
{
	out << "name:" << p._name << "   " << "age:" << p._age << endl;
	return out;
}
void test02()
{
	person arr[] = { { "pxl", 23 },
					 { "dyx", 21 }, 
					 { "wjz", 24 }, 
					 { "ztd", 20 } };
	priority_queue<person, vector<person>, greater<person>> pq(arr, arr + sizeof(arr) / sizeof(arr[0]));//小堆
	pq.push(person("yzc", 22));
	cout <<"堆顶元素是："<< pq.top() << endl;
	while (!pq.empty())
	{
		cout << pq.top() << endl;
		pq.pop();
	}
}
int main()
{
	test02();//自定义类型
	system("pause");
	return 0;
}

⚠️⚠️⚠️注意点：

如果存放自定义类型，我们想要自定义类型像内置类型一样进行各种运算，那么就要在类中重载相应的运算符。
输出自定义类型，需要重载流输出。
在priority_queue的第三个参数时，我们可以用库中的greater函数（头文件：functional），也可以我们自己写一个仿函数（如上述代码）。

三、priority_queue的模拟实现

	template<class T>
	struct less
	{
		bool operator()(const T& x, const T&  y) const
		{
			return x < y;
		}
	};
	template<class T>
	struct greater
	{
		bool operator()(const T& x, const T&  y) const
		{
			return x > y;
		}
	};
	// 优先级队列 -- 大堆 < 小堆 >
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		void AdjustUp(int child)
		{
			Compare comFunc;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (comFunc(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1);
		}
		void AdjustDown(int parent)
		{
			Compare comFunc;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				//if (child+1 < _con.size() && _con[child] < _con[child+1])
				if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1]))
				{
					++child;
				}
				//if (_con[parent] < _con[child])
				if (comFunc(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			assert(!_con.empty());
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}
		const T& top()
		{
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

代码解释：

这里模拟实现底层容器缺省参数使用vector，比较规则使用Less。
这里的比较方式均是自己实现的仿函数。

四、容器适配器

4.1、什么是适配器

适配器是一种设计模式（设计模式是一套被反复使用的，多数人知晓的，经过分类编目的，代码设计经验的总结），该模式是讲一个类的接口转换成客户希望的另一个接口。

4.2、适配模式

在计算机编程中，适配器模式（有时候也称包装样式或者包装）将一个类的接口适配成用户所期待的。一个适配允许通常因为接口不兼容而不能在一起工作的类工作在一起，做法是将类自己的接口包裹在一个已存在的类中。
适配器模式主要应用于，当接口里定义的方法无法满足客户的需求，或者说接口里定义的方法的名称或者方法界面与客户需求有冲突的情况。
两类模式：对象适配器模式 - 在这种适配器模式中，适配器容纳一个它我包裹的类的实例。在这种情况下，适配器调用被包裹对象的物理实体。类适配器模式 - 这种适配器模式下，适配器继承自已实现的类（一般多重继承）。
在计算机编程中，适配器包括：容器适配器、迭代器适配器、泛函适配器等。