【STL】priority_queue的使用和模拟实现

priority_queue的使用和介绍

priority_queue的介绍

优先级队列（priority_queue）它也是一个容器适配器，默认使用的容器是vector，在往队列中放入数据时，它会将容器中放置的数据通过堆算法调整成 大堆/小堆，在使用时我们若不指定建堆方法，它默认会是排大堆（less）

它的使用方法其实和stack，queue类似，只是priority_queue在插入元素的基础上进行了调整建堆

priority_queue的定义方式

1.使用priority_queue创建大堆对象：

priority_queue<int, vector<int>, less<int>> q1;

2.使用priority_queue创建小堆对象:

priority_queue<int ,vector<int>, less<int>> q2;

3.不指定容器和底层使用的堆算法

priority_queue<int> q3;

这时它的容器和堆算法默认使用的是vector<int>和less<int>

priority_queue的接口展示：

priority_queue的模拟实现

模拟实现：

//仿函数/函数对象
//()运算符重载, 使用方式类似于函数调用，所以可以称为:仿函数
//建大堆
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 compare = Less<T>>
class priority_queue
{
	//向上调整, 排大堆
	void AdjustUp(size_t child)
	{
		size_t parent = (child - 1) / 2;

		while (child > 0)
		{
			if (_com(_con[child], _con[parent])) //使用所给比较方式进行比较
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	//向下调整，排大堆
	void AdjustDown(size_t parent)
	{
		compare con; 

		size_t child = parent * 2 + 1;

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

			if (_com(_con[child], _con[parent]))
			{
				swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
public:
	priority_queue()
	{}

	template<class inputiterator>
	priority_queue(inputiterator first, inputiterator last)
	{

		while (first != last)
		{
			_con.push_back(*first);
			++first;
		}

		//大堆
		for (size_t end = (_con.size() - 2) / 2; end >= 0; ++end)
		{
			AdjustDown(end);
		}
	}

	void push(const T& key)
	{
		_con.push_back(key);
		AdjustUp(_con.size() - 1);
	}
	
	void pop()
	{
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		AdjustDown(0);
	}

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

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

	bool empty()
	{
		return _con.empty();
	}
private:
	container _con;
    compare _com;
};