C++ STL：优先级队列priority_queue的使用方法和模拟实现_std::priority_queue

目录

一. 什么是priority_queue

二. priority_queue常见接口的使用

三. priority_queue的模拟实现

3.1 仿函数

3.2 构造函数的模拟实现

3.3 插入数据函数的模拟实现

3.4 删除堆顶数据函数的模拟实现

3.4 判空、统计数据量及获取堆顶数据函数的模拟实现

附录：优先级队列priority_queue的模拟实现完整代码

---

一. 什么是priority_queue

优先级队列priority_queue，即数据结构中的堆，堆是一种通过使用数组来模拟实现特定结构二叉树的二叉树的数据结构，根据父亲节点与孩子节点的大小关系，可以将堆分为大堆和小堆：

• 大堆：所有父亲节点的值都大于或等于它的孩子节点的值。
• 小堆：所有父亲节点的值都小于或等于它的孩子节点的值。

在C++ STL中，priority_queue的声明为：template <class T, class Container = vector<T>, class Compare = std::less<T>>  class priority_queue;

其中，每个模板参数的含义为：

• T：优先级队列中存储的数据的类型
• Container：用于实现优先级队列的容器，默认为vector
• Comapre：比较仿函数，用于确定是建大堆还是建小堆。Compare默认为std::less<T>，建大堆，如果要建小堆，需要显示传参std::greater<T>，同时还有显示的声明容器类型。

二. priority_queue常见接口的使用

#include<iostream>
#include<queue>
#include<functional>
 
int main()
{
	std::priority_queue<int> maxHeap;   //建大堆
	int data[10] = { 56,12,78,23,14,34,13,78,23,97 };
	//让arr中的数据依次入大堆
	for (int i = 0; i < 10; ++i)
	{
		maxHeap.push(data[i]);
	}
 
	std::cout << maxHeap.empty() << std::endl;  //判空 -- 0
	std::cout << maxHeap.size() << std::endl;   //获取堆中数据个数 -- 10
 
	//依次提取大堆堆顶数据并打输出
	while (!maxHeap.empty())
	{
		//97 78 78 56 34 23 23 14 13 12
		std::cout << maxHeap.top() << " ";
		maxHeap.pop();
	}
	std::cout << std::endl;
 
	std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;  //建小堆
	//让arr中的数据依次入小堆
	for (int i = 0; i < 10; ++i)
	{
		minHeap.push(data[i]);
	}
 
	//依次提取堆顶数据并打输出
	while (!minHeap.empty())
	{
		//12 13 14 23 23 34 56 78 78 97
		std::cout << minHeap.top() << " ";
		minHeap.pop();
	}
	std::cout << std::endl;
 
	return 0;
}

三. priority_queue的模拟实现

这里使用容器vector作为实现优先级队列的默认容器

3.1 仿函数

仿函数，就是使用struct定义的类对象，通过重载操作符()，即operator()(参数列表)实现类似函数的功能。仿函数的调用语法为：

• 类对象名称(参数列表)

直白的说，仿函数其实并不是函数，而是通过在类中定义运算符()的重载函数，通过类对象，来使调用运算符重载函数的语法在功能实现和外观上都与真实的函数一致。

在priority_queue的构造函数中，就经常使用less和greater两个仿函数，less和greater都是C++标准库中给出的判断两数之间大小关系的仿函数，他们被包含在头文件<functional>中：

• less：给两个操作数，判断前者是否小于后者。
• greater：给两个操作数，判断前者是否大于后者。

演示代码3.1，模拟实现了less和greater仿函数，具体的实现方法就是重载运算符()

演示代码3.1：(less和greater的模拟实现)

	template <class T>
	struct Less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};
 
	template <class T>
	struct Greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

综上所述，我们模拟实现的优先级队列，应当包含两个成员变量：

1. Container _con -- 容器。
2. compare _comp -- 用于调用比较函数的类对象。

其中Container和compare都为priority_queue类的模板参数类型，其声明为：

template<class T, class Container = vector<int>, class compare = std::less<T>>

3.2 构造函数的模拟实现

构造函数有两种重载形式：（1）构造空堆，这时构造函数无需额外编写代码进行任何工作，容器成员和_con和类对象_comp都会被调用他们的默认构造函数被创建出来。 （2）通过迭代器区间进行构造，此时先通过迭代器区间构造容器对象，然后执行向下调整建堆操作。

向下调整函数AdjustDown需要有2个参数，分别为：堆中数据个数n和开始向下调整的父亲节点下标parent，其中还会用到类的成员（容器和用于比较的对象），AdjustDown执行的操作依次为（以建大堆为例）：

1. 根据父亲节点的下标，获取其左孩子节点的下标child。
2. 判断孩子节点下标是否越界，如果越界(child>=n)，则函数终止。
3. 判断左孩子节点和右孩子节点那个较大，如果右孩子节点值较大，则将child更新为右孩子节点下标。
4. 判断父亲节点是否小于较大的孩子节点，如果小于，则交换父子节点值，然后将父节点更新为孩子节点，然后回到1继续执行向下调整操作，如果大于或等于，则终止向下调整操作。

注意：对于开始执行向下操作的父节点parent，一定要保证它的左子树和右子树都为大或小堆。

构造函数实现代码：

priority_queue()  //默认构造函数（空堆）
{ }
        
//通过迭代器区间初始
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: _con(first, last)
{
	for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
	{
		adjustDown(_con.size(), i);
	}
}

向下调整函数代码： 

void adjustDown(int n, int parent)  //向下调整函数
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && _comp(_con[child], _con[child + 1]))
		{
			++child;
		}
 
		if (_comp( _con[parent], _con[child]))
		{
			std::swap(_con[parent], _con[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

3.3 插入数据函数的模拟实现

向堆中插入数据需要两步操作：先向容器中尾插数据，然后调用AdjustUp函数上调整数据。

向上调整函数AdjustUp执行的操作流程为：（建大堆为例）

1. 根据开始执行向上调整的孩子节点下标，计算出其父亲节点下标。
2. 判断孩子节点下标是否>0，如果是，继续执行向上调整操作，否则终止函数。
3. 判断孩子节点值是否大于父亲节点，如果大于，交换父子节点值，然后更新孩子节点为当前父亲节点，根据更新后孩子节点下标计算父亲节点下标，然后回到1继续执行向上调整操作。如果孩子节点值小于或等于父亲节点值，那么终止向上调整操作。

向堆中插入数据函数：

void push(const T& x)   //向堆中插入数据函数
{
	_con.push_back(x);  //向容器尾部插入数据
	adjustUp(_con.size() - 1);  //执行向上调整操作
}

向上调整操作函数：

void adjustUp(int child)  //向上调整建堆函数
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_comp(_con[parent], _con[child]))
		{
			std::swap(_con[parent], _con[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

3.4 删除堆顶数据函数的模拟实现

如果直接将除堆顶之外的全部数据向前移动一个单位，那么数组中剩余的数据大概率无法满足堆的结构要求，重新再建堆效率过低。那么，就需要一些额外的技巧来解决问题：

1. 交换堆顶数据和数组中最后一个数据。
2. 将数组中的最后一个数据删除。
3. 以当前根节点为起始父亲节点，执行向下调整操作，使数组中的数据重新满足堆的结构。

void pop()  //删除堆顶数据
{
	assert(!_con.empty());
			
	std::swap(_con[0], _con[_con.size() - 1]);  //交换堆顶数据和最后面的数据
	_con.pop_back();   //删除容器最后面的数据（即：堆顶数据）
 
	adjustDown(_con.size(), 0);  //执行向下调整操作
}

3.4 判空、统计数据量及获取堆顶数据函数的模拟实现

size_t size()  //获取堆中数据个数
{
	return _con.size();
}
 
bool empty()  //判空
{
	return _con.empty();
}
 
const T& top()  //获取堆顶数据（根节点数据）
{
	assert(!_con.empty());  
	return _con[0];
}

附录：优先级队列priority_queue的模拟实现完整代码

#include<vector>
#include<functional>
#include<cstdbool>
#include<cassert>
 
namespace zhang
{
	template <class T>
	struct Less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};
 
	template <class T>
	struct Greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};
 
	template <class T, class Container = std::vector<T>, class compare = Less<T>>
	class priority_queue
	{
	public:
		priority_queue()  //默认构造函数（空堆）
		{ }
 
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			: _con(first, last)
		{
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
				adjustDown(_con.size(), i);
			}
		}
 
		void push(const T& x)   //向堆中插入数据函数
		{
			_con.push_back(x);  //向容器尾部插入数据
			adjustUp(_con.size() - 1);  //执行向上调整操作
		}
 
		void pop()  //删除堆顶数据
		{
			assert(!_con.empty());
			
			std::swap(_con[0], _con[_con.size() - 1]);  //交换堆顶数据和最后面的数据
			_con.pop_back();   //删除容器最后面的数据（即：堆顶数据）
 
			adjustDown(_con.size(), 0);  //执行向下调整操作
		}
 
		size_t size()  //获取堆中数据个数
		{
			return _con.size();
		}
 
		bool empty()  //判空
		{
			return _con.empty();
		}
 
		const T& top()  //获取堆顶数据（根节点数据）
		{
			assert(!_con.empty());  
			return _con[0];
		}
 
	private:
		void adjustUp(int child)  //向上调整建堆函数
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_comp(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
 
		void adjustDown(int n, int parent)  //向下调整函数
		{
			int child = 2 * parent + 1;
			while (child < n)
			{
				if (child + 1 < n && _comp(_con[child], _con[child + 1]))
				{
					++child;
				}
 
				if (_comp( _con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}
 
	private:
		Container _con;  //存储堆数据的容器
		compare _comp;   //用于实现仿函数的类对象
	};
}