【C++】优先级队列（底层代码解释）

2024-07-14 07:05:09

一. 定义

优先级队列是一个容器适配器，他可以根据不同的需求采用不同的容器来实现这个数据结构，优先级队列采用了堆的数据结构，默认使用vector作为容器，且采用大堆的结构进行存储数据。

（1）在第一个构造函数中的第三个参数中，less是大堆，greater是小堆

（2）第二个构造函数的含义是支持使用容器的迭代器区间进行构造

二. 代码实现与解释

2.1 堆中的向上调整和向下调整

（1）向上调整（插入）

在进行插入时，我们首先将插入的节点放在最后一个位置上，然后进行向上调整。

大堆的向上调整：如果子节点比父节点大则子节点和父节点交换位置

小堆的向上调整：如果子节点比父节点小则子节点和父节点交换位置

（2）向下调整（删除）

在进行删除数据时我们会把第需要删除的一个元素和最后一个元素交换位置，接着删除尾部的元素，然后把第一个元素向下调整到合适的位置。

大堆的向下调整：找到父节点后，再找到左右节点中较大的那个节点，如果父节点小于子节点中较大的那个节点的话，则交换位置

小堆的向下调整：找到父节点后，再找到左右节点中较小的那个节点，如果父节点大于子节点中较大的那个节点的话，则交换位置

以下是大堆的实现:

template<class T,class container = vector<T>>
class priority_queue
{
public:
	void adjust_up(int child)
	{
		Compare com;
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			if (_con[parent]< _con[child])
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}
	void adjust_down(int parent)
	{
		int child = parent * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size()
				&& _con[child ] > _con[child+1])
			{
				++child;
			}
			if ( _con[parent]< _con[child])
			{
				swap(_con[child], _con[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}
	void pop()
	{
		swap(_con[0], _con[size() - 1]);
		_con.pop_back();
		adjust_down(0);
	}
	const& top()
	{
		return _con[0];
	}
	bool empty()
	{
		return _con.empty();
	}
	size_t size()
	{
		return _con.size();
	}
	void push(const T& x)
	{
		_con.push_back(x);
		adjust_up(_con.size()-1);
	}
private:
	container _con;
};

2.2 仿函数

定义：仿函数就是定义一个类，在这个类中我们进行对符号（）进行运算符重载，再用这个类构造一个对象，这个对象可以像函数一样去使用，以下是仿函数的定义与使用。

意义：代替函数指针

Tip：有一点我们需要注意，在C++库的排序函数中，我们想要让函数帮助我们升序或者降序排序时我们也需要传递一个参数给 sort（），但是在这里我们给sort传递的是一个less或者greater类型的对象，而不是像在这里的一个类型。

2.3 任意定义大堆小堆

2.1 中介绍了如何建立一个大堆的结构，那么对于不同的场景，我们也可能使用小堆，那么如果库函数中像2.1这么写的话我们就无法使用小堆了，那么为了解决以上的问题我们提出了以下的解决方案。

在函数模板中写一个仿函数的模板

template<class T,class container = vector<T>,class Compare = Less<T>>

这里的 class container 接收的是一个容器的类型（这里默认使用的是vector），而 class compare接收的是接受的是一个仿函数的类名（默认采用Less）。仿函数Less的作用是返回前者是否小于后者的结果，Greater 的作用是返回前者是否大于后者的结果。

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

有了这两个仿函数我们就可以把向上调整和向下调整的代码调整为以下写法。

用户想建立一个大堆就可以写

priority_queue<int,vector<int>,Less<int>> pq;

建立小堆：

priority_queue<int,vector<int>,Greater<int>> pq;

以下是模拟实现优先级队列的代码

#pragma once
#include<vector>
namespace hjy
{
	template<class T>
	class Less
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};
	template<class T>
	class Greater
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};
	template<class T,class container = vector<T>,class Compare = Less<T>>
	class priority_queue
	{
	public:
		void adjust_up(int child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if(com(_con[parent],_con[child]))
				//if (_con[parent]< _con[child])
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}
		void adjust_down(int parent)
		{
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				/*if (child + 1 < _con.size()
					&& _con[child ] > _con[child+1])*/
				if (child + 1 < _con.size()
					&&com(_con[child],_con[child+1]))
				{
					++child;
				}
				if(com(_con[parent]<_con[child]))
				//if ( _con[parent]< _con[child])
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}
		void pop()
		{
			swap(_con[0], _con[size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		const& top()
		{
			return _con[0];
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size()-1);
		}
	private:
		container _con;
	};
}

码农公寓