pop_back() ：删除容器尾部元素

5. 标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用vector 。

6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、 push_heap 和 pop_heap 来自动完成此操作。

特点： 按照数据优先级出队列（底层是堆，默认大堆）

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

函数声明	接口说明
priority_queue()/priority_queue(first, last)	构造一个空的优先级队列
empty( )	检测优先级队列是否为空，是返回 true ，否则返回 false
top( )	返回优先级队列中最大 ( 最小元素 ) ，即堆顶元素
push(x)	返回优先级队列中最大 ( 最小元素 ) ，即堆顶元素
pop ()	删除优先级队列中最大 ( 最小 ) 元素，即堆顶元素

#include<iostream>
#include<queue>
#incldue<deque>
void test5()
{
	priority_queue<int> pq;
	pq.push(5);
	pq.push(1);
	pq.push(8);
	pq.push(10);
	pq.push(-5);
	cout <<"size:"<< pq.size() << endl;//输出数据个数
	while (!pq.empty())
	{
		cout << pq.top() << " ";//输出堆顶元素；
		pq.pop();//删除堆顶元素
	}
	cout << endl;
}

2.2.3priority_queue模拟实现

我们可以看到文档中对priority_queue的介绍是三个参数

怎么比平常多了一个参数，第三个参数是干嘛的呢？

我们说了，优先级队列底层是堆实现的，默认是大堆，如果我们不想用大堆呢？想让数据从小到大以小堆排列怎么办？所以这里的第三个参数就是用来改变默认大小堆的，这里是用仿函数控制的。

我们按照之前的方法把priority_queue的基础接口写出来。

namespace A
{
   template<class T, class Container = vector<T>>
class priority_queue
{
public:
	
	void push(const T& x)
	{
		_con.push_back(x);
	}
	void pop()
	{
		_con.pop_back();
	}
	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
	T& top()
	{
		return _con[0];
	}
private:
	Container _con;
};
}

然后我们看，优先级队列的底层是堆，那插入一个数据和删除一个数据之后都需要保证仍然是堆，所以我们还需要写出堆的两个重要组成——向上调整和向下调整。默认是大堆Less，所以我们按照库里面的习惯认为Less是大堆，建大堆。

void adjust_up(size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_con[parent] < _con[child])
		{
			std::swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
	else
	{
		break;
	}
	}
}
void adjust_down(size_t parent)
{
	size_t child = parent * 2 + 1;;
	while (child < _con.size())
	{
		if (child + 1 < _con.size() && _con[child] < _con[child+1])
		{
			child++;
		}
		if (_con[parent] < _con[child])
		{
			std::swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;;
		}
		else
		{
			break;
		}
	}
}

然后再补全push和pop两个接口。

void push(const T& x)
{
	_con.push_back(x);
	adjust_up(_con.size() - 1);
}
void pop()
{
	std::swap(_con[0], _con[_con.size() - 1]);
	_con.pop_back();
	adjust_down(0);
}

这种写法是默认大堆的写法，如果我们想建小堆呢？再写一个小堆的向上和向下调整吗？

这样太麻烦，C++语言非常忌讳重复代码，所以我们这里用仿函数解决。

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;
	}
};

然后我们可以给priority_queue的参数传第三个参数Compare

template<class T, class Container = vector<T>, class Compare = Less<T>>

这样，默认是大堆Compare=Less<T>,如果想建小堆，直接可以把Less换成Greater;

然后把向上调整和向下调整部分父子比较部分可以用仿函数比较

这样就好了。

修改之后的完整代码为

namespace A
{
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
{
public:
	void adjust_up(size_t child)
	{
		Compare com;
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			if (com(_con[parent], _con[child]))
			{
				std::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() && com(_con[child], _con[child + 1]))
			{
				child++;
			}
			if (com(_con[parent], _con[child]))
			{
				std::swap(_con[child], _con[parent]);
				parent = child;
				child = parent * 2 + 1;;
			}
			else
			{
				break;
			}
		}
	}
	void push(const T& x)
	{
		_con.push_back(x);
		adjust_up(_con.size() - 1);
	}
	void pop()
	{
		std::swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		adjust_down(0);
	}
	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
	T& top()
	{
		return _con[0];
	}
private:
	Container _con;
};
}

我们测试

void test6()
{
	A::priority_queue<int,vector<int>,A::Greater<int>> pq;//小堆
	pq.push(10);
	pq.push(1);
	pq.push(-10);
	pq.push(100);
	cout << "size:" << pq.size() << endl;
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;

}

程序正常运行且结果与预期相符

好啦，这次到这里就结束了，期待下次和大家分享！