C++从入门到起飞之——priority_queue(优先级队列) 全方位剖析！

admin管理员组

文章数量:1606961

🌈个人主页：秋风起，再归来~
🔥系列专栏：C++从入门到起飞          
🔖克心守己，律己则安

目录

1、priority_queue的介绍

2、priority_queue的使用

3、priority_queue的模拟实现 

3.1、仿函数的介绍

3.2、模拟实现源码

4、完结散花

---

1、priority_queue的介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素 中最大的。

2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶 部的元素)。

3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的 顶部。

4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过 随机访问迭代器访问，并支持以下操作：

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

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

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

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

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

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue 类实例化指定容器类，则使用vector。

6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用 算法函数make_heap、push_heap和pop_heap来自动完成此操作。

2、priority_queue的使用

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

3、priority_queue的模拟实现 

3.1、仿函数的介绍

在之前的文章中我提到过关于sort第三个参数的问题，当时我称他为比较器，事实上它更仿函数有关！

 仿函数其实就是一个类里面进行了操作符（）的重载，我们用这个类实例化一个对象再调用它重载的（）就可以比较两个元素的大小！

下面举一个简单的示例代码：

template<class T>
class compareLess
{
public:
	bool operator()(const T& a1,const T& a2)
	{
		return a1 < a2;
	}
};

int main()
{
	compareLess<int> less;
	int a = 30;
	int b = 20;
	cout<<less.operator()(a,b)<<endl;
	return 0;
}

//cout<<less.operator()(a,b)<<endl;
cout<<less(a,b)<<endl;

重载函数的调用可以简化为 less(a,b)，我们会发现它的调用形式和函数非常相像，不同的是less是我们实例化出来的对象的名字，并不是函数名，因此，我们称其为仿函数！

现阶段我们看到仿函数看起来非常简单，确实如此，不过，我们在后面会遇到和仿函数有关的更为复杂的内容！

好啦，我们再来看到优先级队列，我们会发现它的模版参数里面也有仿函数的身影，原因也很简单，我们知道优先级队列就是堆，那我们在实现堆的时候必然会用到向上和向下调整的算法。而这些算法也一定会有元素的大小比较，如果我们在类里面实现的是一个大堆，那我们下次要用到小堆的时候怎么办呢！难道临时打电话给程序员叫他修改一下比较符号吗？显然不可能，难道实现俩个类吗，这两个类的代码高度相似，只有一些比较大小的符号不同，这样做并不合理。

这时候我们就可以通过传递比较器的方法来解决这个问题了！ 

//向上调整
void AdjustUp()
{
	//用比较器实例化一个对象
	compare comp;
	int child = con.size() - 1;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//仿函数取大向上调整
		if (comp(con[parent], con[child]))
		{
			swap(con[child], con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

在优先级队列实例化出对象之前，我们不知道你具体的比较逻辑！只有使用者在传递模版参数之后才可以确定！

3.2、模拟实现源码

这篇文章的主要目的是让我们初步了解仿函数并熟悉priority_queue，至于priority_queue的模拟实现其实非常简单（如果我们之前对数据结构中的堆学的还不错的话，这两个向上和向下调整算法也是手到擒来的！）下面我就直接给源码给大家参考一下了！

#pragma once

#include<iostream>
#include<algorithm>
#include<list>
#include<vector>
#include<deque>

using namespace std;

namespace my_priority_queue
{
	//仿函数（比较器）
	template<class T, class container = vector<T>, class compare = less<T>>
	class priority_queue
	{
	public:
		//元素数量
		size_t size()
		{
			return con.size();
		}
		//判空
		bool empty()
		{
			return con.size() == 0;
		}
		//向上调整
		void AdjustUp()
		{
			//用比较器实例化一个对象
			compare comp;
			int child = con.size() - 1;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//仿函数取大向上调整
				if (comp(con[parent], con[child]))
				{
					swap(con[child], con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		//入栈
		void push(const T& val)
		{
			con.push_back(val);
			//向上调整
			AdjustUp();
		}
		//向下调整
		void AdjustDown()
		{
			compare comp;
			int parent = 0;
			int child = parent * 2 + 1;//左孩子
			while (child < con.size())
			{
				//如果右孩子更大就更新孩子
				if ((child < con.size() - 1 )&& comp(con[child ], con[child+1]))
				{
					child++;
				}
				//仿函数向下调整
				if (comp(con[parent], con[child]))
				{
					swap(con[child], con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		//出栈
		void pop()
		{
			swap(con[0], con[con.size() - 1]);
			con.pop_back();
			AdjustDown();
		}
		//取优先级高元素
		const T& top()
		{
			return con[0];
		}
	private:
		container con;
	};

}

4、完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~

本文标签： 优先级队列入门priorityqueue