【c++丨STL】priority_queue（优先级队列）的使用与模拟实现

ephemerals__

发布于 2024-11-26 12:14:51

7490

文章被收录于专栏：ephemerals__的技术专栏ephemerals__的技术专栏

前言

之前我们学习了STL中的两个容器适配器：stack和queue。本篇文章，我们将学习另一个容器适配器：priority_queue（优先级队列），并尝试模拟实现。

一、priority_queue简介

优先级队列是一种容器适配器，根据某种严格的弱排序标准，特别设计为它的第一个元素总是它所包含的元素中的最大元素。

虽然它的名字叫“优先级队列”，但实际上它跟队列没有什么关系，它的底层结构是堆。如果你对堆这一数据结构并不是很了解，可以参阅这篇文章：

【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）_树形结构编译器-CSDN博客

既然它的底层结构是一个堆，那么它也就符合堆的所有性质，例如不能遍历、只能从堆顶出入数据等。使用priority_queue时，需要引头文件<queue>。

作为一棵顺序存储的完全二叉树，priority_queue也通过复用其他容器来实现（一般是vector），因此作为一个容器适配器而存在。需要特别注意的是，它的模板参数中有一个仿函数，可以用于控制生成大堆或者小堆（默认是大堆）。

话不多说，我们开始逐一介绍它的常用接口。

二、priority_queue的使用

priority_queue的成员函数如下：

构造函数(constructor)

priority_queue常用的构造函数有两个：

函数原型	功能说明
priority_queue();	无参构造，创建一个空的优先级队列
priority_queue(InputIterator first, InputIterator last);	迭代器区间构造

代码示例：

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

int main()
{
	priority_queue<int> pq1;//无参构造

	vector<int> arr = { 1,2,3,4,5 };
	priority_queue<int> pq2(arr.begin(), arr.end());//迭代器区间构造
	return 0;
}

empty

empty的作用是判断优先级队列是否为空。如果为空，返回true；否则返回false。

代码示例：

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

int main()
{
	priority_queue<int> pq1;//无参构造

	vector<int> arr = { 1,2,3,4,5 };
	priority_queue<int> pq2(arr.begin(), arr.end());//迭代器区间构造

	cout << pq1.empty() << endl;
	cout << pq2.empty() << endl;
	return 0;
}

size

size的作用是获取优先级队列中的元素个数。代码示例：

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

int main()
{
	priority_queue<int> pq1;//无参构造

	vector<int> arr = { 1,2,3,4,5 };
	priority_queue<int> pq2(arr.begin(), arr.end());//迭代器区间构造

	cout << pq1.size() << endl;
	cout << pq2.size() << endl;
	return 0;
}

top

top函数用于获取队头（堆顶）的元素。代码示例：

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

int main()
{
	vector<int> arr = { 2,1,3,5,4 };
	priority_queue<int> pq(arr.begin(), arr.end());

	cout << pq.top() << endl;
	return 0;
}

push和pop

push的功能是插入一个数据到优先级队列当中。当然，数据插入之后，函数会调用向上调整算法使整个结构保持堆的性质。

pop的功能是删除队头（堆顶）数据。删除之后，函数会调用向下调整算法来保持堆结构的性质。

代码示例：

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

int main()
{
	priority_queue<int> pq;

	pq.push(3);
	pq.push(4);
	pq.push(2);
	pq.push(1);
	pq.push(5);

	while (!pq.empty())//非空则循环出数据
	{
		cout << pq.top() << ' ';
		pq.pop();
	}
	cout << endl;
	return 0;
}

swap

swap用于交换两个优先级队列的数据。

仿函数的使用

之前已经提到，pritority_queue的模板参数中有一个仿函数，可以支持创建大堆或者小堆。STL提供了两个仿函数：less和greater。我们传入less时，生成大堆；greater生成小堆（这里个人认为是设计的一大败笔，与其他容器和算法的使用含义刚好相反）。这里需注意以下几点：

1. priority_queue的模板参数顺序依次是：元素类型、容器、仿函数。所以我们需要显示传仿函数时，需要先传入元素类型和容器的模板参数。 2. 元素类型也要传给容器和仿函数的模板参数。 3. 如果元素是我们自己定义的类，则这些元素之间比较大小的逻辑需要我们自己通过运算符重载去定义，然后将类型传给仿函数。

接下来，我们尝试使用仿函数创建一个大堆和一个小堆：

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

int main()
{
	priority_queue<int> pq1;//大堆

	pq1.push(3);
	pq1.push(4);
	pq1.push(2);
	pq1.push(1);
	pq1.push(5);

	cout << "pq1:";
	while (!pq1.empty())
	{
		cout << pq1.top() << ' ';
		pq1.pop();
	}
	cout << endl;

	priority_queue<int, vector<int>, greater<int>> pq2;//小堆

	pq2.push(3);
	pq2.push(4);
	pq2.push(2);
	pq2.push(1);
	pq2.push(5);

	cout << "pq2:";
	while (!pq2.empty())
	{
		cout << pq2.top() << ' ';
		pq2.pop();
	}
	cout << endl;
	return 0;
}

三、priority_queue的模拟实现

学习了优先级队列的使用之后，我们尝试模拟实现一个优先级队列。

首先是仿函数的实现：

//仿函数
template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y) const
	{
		return x < y;
	}
};
template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

在仿函数实现当中，我们首先定义两个类分别重载函数调用操作符，然后在函数内判断大小即可。注意less是小于，greater是大于。

接下来是容器适配器的实现：

template<class T, class Container = vector<T>, class Compare = Less<T>>
class PriorityQueue
{
public:
	//强制生成默认构造
	PriorityQueue() = default;

	//迭代器区间构造
	template<class InputIterator>
	PriorityQueue(InputIterator first, InputIterator last)
		:_con(first, last)
	{
		for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)//对区间内的数据从后往前进行向下调整
		{
			AdjustDown(i);
		}
	}

	//取堆顶数据
	const T& top()
	{
		return _con[0];
	}

	//判空
	bool empty()
	{
		return _con.empty();
	}

	//入堆
	void push(const T& x)
	{
		_con.push_back(x);
		AdjustUp(_con.size() - 1);
	}
	//向上调整算法
	void AdjustUp(size_t child)
	{
		Compare com;//仿函数定义
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			if (com(_con[parent], _con[child]))
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	//出堆
	void pop()
	{
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		AdjustDown(0);
	}
	//向下调整算法
	void AdjustDown(size_t parent)
	{
		Compare com;//仿函数定义
		size_t child = parent * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
			{
				child++;
			}
			if (com(_con[parent], _con[child]))
			{
				swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
private:
	Container _con;//容器
};

可以发现，与stack和queue相同，我们都是在函数体内部调用了封装容器的接口。这里需要注意迭代器区间构造的实现逻辑还有向上/向下调整算法的大小判断，以保证less默认建大堆，greater默认建小堆。