[C++知识库]STL——理解priority_queue

1、priority_queue基本介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问。
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

2、priority_queue的常用接口及其使用

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

点击查看文档中priority_queue的细节

3、priority_queue模拟实现

3.1 仿函数Less和Great

//通过使用仿函数来达到使用者能够轻易改变优先级
template<class T>
struct Less   //大的优先级高，建大堆，升序
{
	bool operator()(const T& x1, const T& x2) const
	{
		return x1 < x2;
	}
};

template<class T>
struct Greater//小的优先级高，建小堆，降序
{
	bool operator()(const T& x1, const T& x2) const
	{
		return x1 > x2;
	}
};

//为什么Less和Greater实现的功能恰好相反，因为库里的也是这么实现的，所以我们也这样实现

3.2 adjust_up和adjust_down

template<class T, class Container = vector<int>, class Compare = Less<T>>
class priority_queue
{
//把这两个调整算法写为私有，因为使用者不需要知道底层实现，这也很好的体现了封装性
private:      
	void adjust_up(size_t child)//向上调整
	{
		Compare com;
		size_t parent = (child - 1) / 2;//从第一个非叶子结点开始调节
		while (child > 0)//注意：这里一定是child>0，不需要写>=，因为当child=0时，child已经是根结点了，不需要调整了
		{
			//if (_con[child] > _con[parent])
			if (com(_con[parent], _con[child]))//——》_con[parent] < _con[child]
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else//不满足条件时，调整就已经结束了
			{
				break;
			}
		}
	}

	void adjust_down(size_t parent)//向下调整
	{
		Compare com;
		size_t child = parent * 2 + 1;//默认是左孩子小
		while (child < _con.size())
		{
			//if (child + 1 < _con.size() && _con[child + 1] > _con[child])
			if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))//_con[child] < _con[child + 1]
			{
				child += 1;//如果右孩子大，就加1
			}
			//if (_con[child] > _con[parent])
			if (com(_con[parent], _con[child]))//_con[parent] < _con[child]
			{
				swap(_con[child], _con[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
}

如果不了解堆以及堆的调整算法，请点击——》数据结构——二叉树的顺序结构—堆

3.3 priority_queue的定义

template<class T, class Container = vector<int>/*缺省值给vector<int>*/, class Compare = Less<T>>
class priority_queue
{
public:

	priority_queue()//如果是内置类型，或者STL都不需要写，如果是自定类型就需要写，析构函数也一样
	{}
	
	~priority_queue()
	{}

	template<class InputIterator>
	priority_queue(InputIterator first, InputIterator last)
		:_con(first, last)//通过迭代器区间初始化
	{
		for (int i = (_con.size() - 2) / 2; i >= 0; i--)
		{
			adjust_down(i);
		}
	}
    //如果需要使用向下调整算法建小(大)堆，就需要保证左右都是小(大)堆，
    //所以我们就需要从最后一个非叶子节点开始调整，直到将第一个结点也调整完为止
    

	void push(const T& x)
	{
		_con.push_back(x);
		adjust_up(_con.size() - 1);//插入数据后，堆的结构就被破坏了，所以需要从新向上调整
	}

	void pop()
	{
		assert(!_con.empty());
		swap(_con[0], _con[_con.size() - 1]);//删除数据我们只需要将第一个数据和最后一个数据互换，再将size-1，就达到了删除的效果
		_con.pop_back();
		adjust_down(0);//因为第一个数据和最后一个数据互换了，堆结构已经被破坏，所以需要向下调整

	}

    //获取元素个数
	size_t size() const
	{
		return _con.size();
	}
    
    //获取优先级最高的元素
	const T& top()
	{
		return _con[0];
	}

    //判断priority_queue是否为空
	bool empty()
	{
		return _con.empty();
	}

private:
	Container _con;//通过模板来构造_con
};