当前位置：首页 > article >正文

priority_queue底层实现细节

article 2025/1/23 8:49:43

一、priority_queue介绍

优先级队列只提供了 push() pop() top() 函数，本质是一个堆，所以只有堆顶的元素有意义。

本质也是容器适配器，用的是 vector，就像数据结构阶段实现的堆一样，但是由于模板的引入，在这里的优先级队列支持传入比较函数对象来实现不同情况的比较，从而使堆顶的 top 是符合要求的。

priority_queue 与 sort 的对比

两者都是通过传入比较函数对象来实现特定的比较，但是底层是不同的。

（1）priority_queue 是通过模板参数来接受收比较函数对象的，sort 函数是通过函数参数来接受比较函数对象的。

（2）所以一个是类模板传类型，一个是函数模板传对象。

二、部分代码展示

#pragma once
#include<vector>
using namespace std;
namespace bit
{
	template<class T>
	struct Less
	{
		bool operator(const T& x1, const T& x2)
		{
			return x1 < x2;
		}
	};

	template<class T>
	struct Greater
	{
		bool operator(const T& x1, const T& x2)
		{
			return x1 > x2;
		}
	};

	// 默认传递大堆，类模板传类型，函数模板传对象（要有()）
	template<class T, class Container = vector<T>, class Cmp = Less<T>>
	class priority_queue
	{
	public:
		void adjustup(size_t child)
		{
			Cmp cmp;
			// 0 1 2
			int parent = (child - 1) / 2;
			while (child > 0) 
			{
				if (cmp(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}
		void adjustdown(size_t parent)
		{
			Cmp cmp;
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && cmp(_con[child], _con[child + 1]))
					child++;
				if (cmp(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
			
		}

		void push(const T& x)
		{
			_con.push_back();
			adjustup(_con.size() - 1);
		}

		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjustdown(0);
		}
		
		bool empty()
		{
			return _con.size() == 0;
		}

		const T& top()
		{
			return _con[0];
		}

		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}