使用

priority_queue

优先级队列与 stack 和 queue 一样，也是一个容器适配器，其底层通过 vector 来实现的。与 stack 和 queue 不同的是，它的第一个元素总是它所包含的元素中最大或最小的一个。

也就是说，优先级队列就是数据结构中所说的堆。其通过堆的向上调整算法、向下调整算法等，将其变为一个堆，保证其第一个元素一定为其所包含元素中最大或最小的一个。

priority_queue<int> q;
q.push(9);
q.push(2);
q.push(7);
q.push(1);
q.push(5);

while (!q.empty())
{
	cout << q.top() << " ";
	q.pop();
}
cout << endl;

模拟实现

基础实现

模拟实现优先级队列就是模拟实现堆，要实现的核心接口为 push() 和 pop() 。(堆的实现详解)

其为适配器，底层利用 vector 来实现。

默认实现为大堆。

#include<vector>

//大堆
namespace Friend
{
	template<class T, class Container = vector<T>>
	class priority_queue
	{
	public:
		bool empty() const
		{
			return con.empty();
		}

		size_t size() const
		{
			return con.size();
		}

		const T& top() const
		{
			// 返回数组的第一个元素
			return con.front();
		}

		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;

			while (parent >= 0)
			{
				if (con[parent] < con[child])
				{
					std::swap(con[parent], con[child]);

					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void AdjustDown(int parent)
		{
			int child = 2 * parent + 1;

			while (child < con.size())
			{
				if (child + 1 < con.size() && con[child] < con[child + 1])
				{
					child++;
				}

				if (con[parent] < con[child])
				{
					std::swap(con[parent], con[child]);

					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			// 在尾部插入一个新数据
			con.push_back(x);

			// 将其重新调整为堆
			AdjustUp(con.size() - 1);
		}

		// 删除堆顶的数据
		void pop()
		{
			// 交换堆顶和尾部的数据
			std::swap(con[0], con[con.size() - 1]);

			// 删除尾部数据
			con.pop_back();

			// 将其重新调整为堆
			AdjustDown(0);
		}

	private:
		Container con;
	};
}

仿函数

按照之前的方法，如果要把大堆变为小堆，就要把 AdjustUp( )、AdjustDown( ) 中所有的 ‘<' 变为 ’>'  ，十分麻烦。因此，C++ 中使用仿函数来解决这个问题。

仿函数实际上为类，并非真正的函数。

其通过重载了 ( ) ，来控制大堆、小堆的变化。

template<class T>
class Less
{
public:
	// x -- i-1  *******  y -- i
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
class Greater
{
public:
	// x -- i-1  *******  y -- i
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

由于其调用时像函数调用，因此得名仿函数。

Less<int> less;

less(10, 20);
less.operator()(1, 9);

Greater<int> greater;

greater(10, 20);
greater.operator()(1, 9);

改进

因此，我们对代码进行改进。

namespace Friend
{
	template<class T, class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	public:
		bool empty() const
		{
			return con.empty();
		}

		size_t size() const
		{
			return con.size();
		}

		const T& top() const
		{
			// 返回数组的第一个元素
			return con.front();
		}

		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;

			while (parent >= 0)
			{
				// if (con[parent] < con[child])
				if (com(con[parent], con[child]))
				{
					std::swap(con[parent], con[child]);

					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void AdjustDown(int parent)
		{
			int child = 2 * parent + 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 (con[parent] < con[child])
				if (com(con[parent], con[child]))
				{
					std::swap(con[parent], con[child]);

					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			// 在尾部插入一个新数据
			con.push_back(x);

			// 将其重新调整为堆
			AdjustUp(con.size() - 1);
		}

		// 删除堆顶的数据
		void pop()
		{
			// 交换堆顶和尾部的数据
			std::swap(con[0], con[con.size() - 1]);

			// 删除尾部数据
			con.pop_back();

			// 将其重新调整为堆
			AdjustDown(0);
		}

	private:
		Container con;
		Compare com;
	};
}

大堆时：

Friend::priority_queue<int> q;

如果要变为小堆，则：

Friend::priority_queue<int, vector<int>, Greater<int>> q;

只需通过仿函数的变换就能达到目的。