• 优先队列的上下文环境是堆，堆中能够任意插入元素，但是只支持访问最大堆元素（也就是优先队列中的顶部元素）
• 优先队列同样是一种容器适配器，它封装了一个底层标准容器，暴露了堆需要所需要的底层容器的一些必要操作，隐藏了不需要的操作
• 优先队列封装的底层容器可以是标准容器，也可以是其他特定设计的容器，但是这个容器必须要支持随机访问迭代器：
  • empty()：检测容器是否为空
  • size()：返回容器中有效元素个数
  • front()：返回容器中第一个元素的引用
  • push_back()：在容器尾部插入元素
  • pop_back()：删除容器尾部元素
• 标准容器中vector和deque是满足这些条件的，在没有指定底层容器的情况下，默认将vector作为标准容器
• 至于为什么要底层要能够支持随机访问迭代器呢？这是为了方便随时在内部构造堆。容器适配器会在需要的时候调用算法函数，例如make_leap、push_leap、pop_heap等

---

1.2. priority_quere的使用

优先队列使用vector作为底层容器，并且在vector中加入堆算法，将vector构造成了一个堆，所以可以说优先队列就是一个堆，所以在碰见堆的时候就要想到优先队列。（默认情况下，priority_queue是一个大堆）

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

我们来看一下下面的代码：

代码语言：javascript

AI代码解释

int main()
{
	vector<int> v = { 3,2,5,7,1,10,9,8,6,4 };
	priority_queue<int> q1;
	for (auto& e : v)
		q1.push(e);
 
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
 
	cout << endl;
 
	//如果要创建小堆，将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}
 
 
	return 0;
}

运行结果：

很明显在没有特殊说明的情况下，直接top()打印priority_queue是从大到小的（说明是一个大堆）。但是我们通过调整priority_queue的第三个参数，也就是前面我们提到的比较规则将弱排序改为greater<>即可实现小顶堆。

1.2.1. 重载<、>

如果priority_queue中包含了自定义类型话，因为需要使用比较器，所以需要对运算符<、>进行重载。

我们使用之前实现过的Date时间类举一个例子：

代码语言：javascript

AI代码解释

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{
	}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& _cout, const Date& d)
	{
		_cout << d._year << "-" << d._month << "-" << d._day;
		return _cout;
	}
private:
	int _year;
	int _month;
	int _day;
};
void TestPriorityQueue()
{
	// 大堆，需要用户在自定义类型中提供<的重载
	priority_queue<Date> q1;
	q1.push(Date(2025, 9, 18));
	q1.push(Date(2025, 9, 19));
	q1.push(Date(2025, 9, 20));
	cout << q1.top() << endl;
	// 如果要创建小堆，需要用户提供>的重载
	priority_queue<Date, vector<Date>, greater<Date>> q2;
	q2.push(Date(2025, 9, 19));
	q2.push(Date(2025, 9, 18));
	q2.push(Date(2025, 9, 20));
	cout << q2.top() << endl;
}

运行结果：

---

1.3. priority_queue的模拟实现

我们现在已经清楚了，优先队列就是一个堆，并且底层容器是vector，并且默认情况下是最大堆，所以实现起来还是比较好实现的：