📌 创作初心：在构建个人知识体系的同时，希望帮助更多正在学习 STL 的同学

📚 系列专栏：柯一梦的STL进阶之路

🌐 个人主页：
👉 Gitee
👉 GitHub

💡 座右铭：功不唐捐，玉汝于成

🎯 本文目标：

  • 理解 priority_queue 的底层结构（堆）
  • 掌握向上调整 / 向下调整算法
  • 搞懂仿函数在 STL 中的作用
  • 手写实现一个简化版 priority_queue

🧠 阅读建议：本文偏底层实现，建议先掌握 vector 和基础模板知识再阅读

priority_queue的介绍

priority_queue的介绍

priority_queue是一个具有heap风格的vector，是vector的容器适配器。因为建堆的过程需要很多下标访问，而vector的下标访问效率更极致，所以我们选择使用vector而不是deque。

priority_queue的定义方式

priority_queue有三个模版参数：所储存的数据类型，底层容器，建造大堆还是小堆

  1. 使用vector作为底层容器，内部构造大堆结构
1
priority_queue q<int,vector<int>,less<int>>
  1. 使用vector作为底层容器，内部构造小堆结构
1
priority_queue q<int,vector<int>,greater<int>>
  1. 不指定使用某个容器和内部需要够造的堆结构
1
priority_queue q<int>

===注意===：优先级队列的底层默认使用vector作为底层容器，并且构造大堆结构

priority_queue各个接口的介绍

![][https://cdn.jsdelivr.net/gh/Ruxiangjie/image@main/img/Pasted%20image%2020260317161700.png]
==重点：构造函数参数讲解==

既然有了模版参数，这个构造函数为什么还要写这么多的参数，并且后面带上默认缺省值呢？

1.当我们写构造函数不传参的时候，Container默认是vector，在构造函数的参数列表里进行了：调用了vector的默认构造，并且对其进行引用，然后把vector里面的值push进底层容器中
2.这样设计是为了你能够传入一个里面有值的vector；带上缺省值是为了不需要重新再写一个默认构造函数

priority_queue的实现

堆的向上调整算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void adjust_up(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;
		}
	}
}

在我们插入数据的时候会用到堆的向上调整算法，因为我们默认建的堆是大堆，所以会从最后向上与父母不断的比较。在书写的时候我们要记住一个口诀，就是先写一个while循环，然后再while循环里写if的比较结构，来判断是否需要去交换数据，在交换完数据以后要记得更新child和parent，while循环的结束条件就是child和0的大小比较。

堆的向下调整算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void adjust_down(size_t parent)
{
	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;
		}
	}
}

我们在删数据和向下建堆的时候会用到向下调整算法。向下调整算法不仅要比较父与子的大小关系，还要确定是哪个孩子要和父母比价大小，是左孩子还是右孩子，这里就又牵扯到一个问题，右孩子存在吗？所以我们要先拍段右孩子是否存在，然后再判断左右孩子大小。

迭代器构造

迭代器构造函数，因为不知道是什么迭代器，所以需要再写一个模版函数。迭代器的种类有很多，虽然外接口都一样，但是内部的标签却不相同
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class T>
class less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};
template<class T>
class greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return y > x;
	}
};

仿函数

所谓的仿函数，就是说具有operator()的类所实例化出来的==对象==可以像函数一样调用。
所以我们在写一个模版类的时候，可以多添加一个模版，传入一个类型，就可以把它实例化出来的对象当做一个函数使用。
就比如我们在写priority_queue的时候，可以多写一个模版参数Compare，用它来控制我们是建大堆还是小堆。其次我们在使用的时候，因为堆里面储存的数据未知，所以用Compare进行比较的仿函数也要写成模版参数。在传入一个类型的时候，记得传入一个less。因为你也不知道堆里面要比较什么数据
完整的priority_queue实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#pragma once
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
namespace rxj
{
	template<class T>
	class less
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};
	template<class T>
	class greater
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return y > x;
		}
	};

	template<class T,class Container = vector<T>,class Compare = less<T>>
	class priority_queue
	{
	private:
		/*void adjust_up()
		{
			if (_con.size() == 1)
				return;
			else
			{
				size_t parents = (_con.size() - 2) / 2;                    
				size_t child = _con.size() - 1;
				while (child != 0&&_con[parents] < _con[child])
				{
					swap(_con[parents], _con[child]);
					child = parents;
					parents = (child - 1) / 2;
				}
			}
		}*/
		//void constructheap_down()
		//{
		//	int parent = (_con.size() - 1) / 2;
		//	while (parent>=0)//如果写while循环，就不要使用size_t类型的变量
		//	{
		//		adjust_down(parent);
		//		--parent;
		//	}
		//}

		void adjust_up(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 adjust_down(size_t parent)
		{
			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() = default;
		/*template<class InputIterator>
		priority_queue(InputIterator first,InputIterator end)
		{
			InputIterator it = first;
			while (it != end)
			{
				_con.push_back(*it);
				++it;
			}
			constructheap_down();
		}*/
		template<class InputIterator>//这是真大神
		priority_queue(InputIterator begin, InputIterator end)
			:_con(begin, end)
		{
			for (int i = (_con.size() - 1) / 2;i >= 0;i--)
			{
				adjust_down(i);
			}
		}

		void push(const T& val)
		{
			_con.push_back(val);
			//向上建堆
			adjust_up(_con.size()-1);
		}

		void pop()
		{
			swap(_con[0],_con[_con.size()-1]);
			_con.pop_back();//我们要先把后面的那个元素删除以后，再去向下调整堆
			adjust_down(0);
		}
		const T& top() const
		{
			return _con[0];
		}
		bool empty()const
		{
			return _con.empty();
		}
	private:
		Container _con;
		Compare com;
	};
}