【C++】priority_queue(STL)优先级队列

Priority_queue官方文档

简介

priority_queue(优先级队列) 是一个容器适配器，它的第一个元素始终是它所包含的元素中最大的一个或是最小的一个。
采用了堆的数据结构。在堆中，元素可以随时插入，并且只能检索最大或最小的元素（优先级队列中最顶端的元素）。
优先级队列底层容器默认是vector，容器可以通过随机访问和迭代器访问。

priority_queue的使用

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

Priority_queue是模板，需要传模板参数。但此模板有默认值，创建大堆时只需要传类型即可。

// 默认创建的是大堆，底层按照小于号比较
 vector<int> v{3,2,7,6,0,4,1,9,8,5};
 priority_queue<int> q1;
 
 for (auto& e : v)
 q1.push(e);
 cout << q1.top() << endl;

而创建小堆，需要将第三个模板参数换成greater比较方式

priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
 cout << q2.top() << endl;

需要注意的是队头元素是不可以修改的，因为top返回的是const引用

Priority_queue底层实现

namespace gf
{
	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 = vector<T>, class Comapre = less<T>>
	class priority_queue
	{
	public:
		void adjust_up(int child)
		{
			Comapre com; // 大于即大堆,小于小堆.通过控制com控制大小与
			int parent = (child - 1) / 2;
			while (child)
			{
				// if (_con[child] > _con[parent])
				if (com(_con[child], _con[parent]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void adjust_down(int parent)
		{
			size_t child = parent * 2 + 1; // 默认左孩子,因为可能没有右孩子
			while (child < _con.size())
			{
				Comapre com;
				// 向上调整时,孩节点只要跟一个父节点比
				// 向下调整时,父节点要跟两个孩节点比,因为父节点可能比一个孩节点大,比另一个孩节点小
				// if (child + 1 < _con.size()
					// && com(_con[child + 1], _con[child]))
				if (child + 1 < _con.size()
					&& com(_con[child + 1], _con[child]))
				{
					++child;
				}

				// if (_con[child] > _con[parent])
				if (com(_con[child], _con[parent]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 - 1;
				}

				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			_con.push_back(x); // 堆是一个数组,尾插向上调整
			adjust_up(_con.size() - 1); // 最后一个位置的数据向上调整
		}

		void pop()
		{
			// 堆直接删效率低,数据也会被打乱
			// 第一个跟最后一个数据交换,尾删然后向下调整
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0); // 向下调整
		}

		const T& top()
		{
			return _con.front();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

	void test_priority_queue()
	{
		// 仿函数
		// 默认是大堆,大的优先级高
		priority_queue<int, vector<int>, greater<int>> pq;
		// priority_queue<int> pq; // 不传参数默认小堆
		// priority_queue<int, deque<int>> pq;
		pq.push(1);
		pq.push(0);
		pq.push(5);
		pq.push(2);
		pq.push(1);
		pq.push(7);

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