priority_queue模拟实现【C++】

全部的实现代码放在了文章末尾

【不了解堆（priority_queue）的可以看我这篇文章：模拟实现堆的接口函数】

priority_queue的模拟实现和stack，queue一样，采用了C++适配器模式

priority_queue的适配器一般是vector，也可以是deque

因为priority_queue是有特殊限制的线性表【只能取堆顶数据，并且需要高效的尾插尾删，还要支持高效的下标访问（因为priority_queue的push和pop一般是调用适配器的尾插，尾删。 实现向下（上）调整算法的时候需要高效的下标访问方法）】
所以只要是线性结构并且可以高效的实现尾插和尾删，支持高效的下标访问的线性表，就可以作为priority_queue的适配器

---

什么是适配器模式？

适配器模式是一种设计模式，它允许将不兼容接口的类一起工作。

适配器模式通常用于以下情况：

1. 希望使用一个类，但其接口与其他代码不兼容。
2. 希望创建一个可重用的类，它能够将接口转换为其他接口。
3. 希望使用第三方库或遗留代码，但其接口与其他代码不兼容。

适配器模式通常包括以下三个主要部分：

1. 目标接口（Target）：这是期望使用的接口，客户端代码只能与目标接口交互。
2. 源接口（Adaptee）：这是需要适配的类，其接口与目标接口不兼容。
3. 适配器（Adapter）：这是一个类，它实现了目标接口，并将调用转换为对源接口的调用。适配器将源接口的调用转换为目标接口的调用，使得客户端代码可以与目标接口交互。

可以类比我们生活中的家庭电源接口和笔记本电脑充电口与电源适配器，它们之间也是一种适配器关系

笔记本电脑充电口是上面提到的目标接口
家庭电源接口是上面提到的源接口
电源适配器是上面提到的适配器

笔记本电脑的充电口是不能和家庭电源接口直接连接进行充电的，因为笔记本电脑用的是直流电，而家庭电源输出的是交流电，所以要把交流电转换为直流电才能给笔记本电脑供电，而电源适配器就能做到这一点

对应了上面提到的适配器模式解决的问题：
可以将不兼容接口的类一起工作

---

准备工作

创建两个文件，一个头文件mypriority_queue.hpp，一个源文件test.cpp

【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件mypriority_queue.hpp中】

1. mypriority_queue.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义

2. test.cpp：存放main函数，以及测试代码

---

包含头文件

1. iostream：用于输入输出
2. vector：提供vector类型的适配对象
3. deque: 提供deque类型的适配对象
4. assert.h:提供assert报错函数

---

定义命名空间

在文件mypriority_queue.hpp中定义上一个命名空间mypriority_queue
把priority_queue类和它的成员函数放进命名空间封装起来，防止与包含的头文件中的函数/变量重名的冲突问题

---

类的成员变量

有两个一个是适配器对象，一个是提供比较的仿函数，默认con是vector类型，comp是std库里面的less

---

什么是仿函数？

C++中的仿函数是指那些能够像函数一样调用的对象，它们的类至少需要有成员函数operator()()。
仿函数可以是任何类型的对象，只要它的类重载了运算符()，它就能够被调用，就可以作为函数使用。
在C++中，标准模板库（STL）中的一些容器算法使用仿函数来封装各种操作，使得这些操作可以应用于容器中的元素。

仿函数可以是用户自定义的，也可以是C++标准库中定义的。例如，STL中的std::less和std::greater就是两个标准的比较仿函数，它们用于排序算法中。用户也可以定义自己的仿函数

总结：
C++的仿函数是重载了operator()的类实例化的对象，它可以被像函数那样调用

举个例子：
下图是一个可以简单进行大于比较的仿函数和它的类

---

比较仿函数在priority_queue中的作用

通过传入不同的仿函数可以做到大堆和小堆之间的切换

【stl库里面是传入less类型的仿函数为大堆，传入greater为小堆。 即大于是小堆，小于是大堆】
为什么呢？
因为priority_queue需要用到比较的地方是向上（下）调整算法
如下图：
【向上（调整）这篇文章不做详细讲解，不了解的可以看我这篇文章：模拟实现堆的接口函数】

根据传给priorit_queue的第三个模板参数的不同，就可以得到不同类型的comp
这样调用comp实现的功能就不一样
std::less类型的comp的功能是判断左参数是否小于右参数
std::greater类型的comp的功能是判断左参数是否大于右参数
通过这一点就可以调整大小堆了
因为
如果comp是小于，那么comp(con[parent],con[child])就是父亲节点<孩子节点就交换，那么就会把大的节点一直往堆顶送，就可以实现大堆
comp是小于的时候同理

---

通过传入不同的仿函数可以做到改变priority_queue里面的比较逻辑

我们使用priority_queue的时候，一般不需要我们传入我们自己写的仿函数，使用库里面的std::less和std::greater就可以满足我们的大部分需求

但是总规有一些情况，库里面的比较仿函数的比较逻辑不符合我们的要求
此时就需要我们自己写一个比较仿函数，传给priority_queue

例
如果我们定义了一个坐标类pos

假设我们比较两个pos对象的大小的时候分两种情况

1. 优先比x，谁的x大谁就大，x相等时y大就大
2. 优先比y，谁的y大谁就大，y相等时x大就大

如果我们用这两种比较方式建出来的堆（priority_queue）肯定是不同的

这个时候库里面的仿函数就满足不了我们的要求了

我们要自己写仿函数：

此时传入不同的仿函数，得到的堆就不同
例

---

构造函数

默认构造

由于默认构造可以直接传入适配器对象，因为传入的适配器对象里面可能已经有数据了，所以要把这些数据给建成堆，就算传入的适配器对象是空的也能处理

例

---

迭代器区间构造

例

---

size

因为把priority_queue的数据都存储在了适配器对象里面

所以适配器对象的size，就是priority_queue的size

加const是为了让const修饰的对象也能调用

size_t size()const
{
	return _con.size();
}
1
2
3
4
5
6
7
8
9
10

---

empty

因为把priority_queue的数据都存储在了适配器对象里面

所以判断适配器对象是否为空即可
加const是为了让const修饰的对象也能调用

bool empty() const
{
	return con.empty();
}
1
2
3
4
5
6
7
8
9

---

top

堆顶的数据只支持读取，  不支持  修改
因为改了就有可能不是 堆 了
所以返回值是const T&

const T& top() const
{
    因为把priority_queue的数据都存储在了适配器对象里面
	而且堆顶的数据存储在适配器对象的第一个数据位置
	所以直接调用front即可
	return con.front();
}
1
2
3
4
5
6
7
8
9
10
11

---

push

void push(const T& val)
{
	因为要把priority_queue的数据都存储在适配器对象里面
	所以新数据，直接尾插到适配器对象里面存储
	con.push_back(val);

	再堆新插入的数据调用向上调整算法
	保持插入之后也还是  堆  结构
	AdiuUp(size() - 1);
}
1
2
3
4
5
6
7
8
9
10

---

pop

void pop()
{
	堆不为空才能删除
	assert(!empty());

	把堆顶与适配器最后一个数据交换
	方便尾删
	std::swap(con[0], con[size() - 1]);

	尾删，把原来的堆顶数据删除
	con.pop_back();

	对换到堆顶的数据进行向下调整算法
	保持删除之后也还是  堆  结构
	AdiuDown(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

全部代码

#include<iostream>
#include<vector>
#include<deque>
#include<assert.h>
using namespace std;

namespace mypriority_queue
{
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	private:
		//拥有比较大小能力的仿函数
		Compare comp;

		//适配器对象
		Container con;
	    
		//向上调整算法
		void AdiuUp(int child)
		{
			//找到  逻辑结构  中的父亲节点
			int parent = (child - 1) / 2;

			while (child > 0)
			{
				//使用  比较仿函数comp  进行比较大小
				//默认的comp是 std::less 类型的
				//即  左参数<右参数  就返回true，否则返回false
				if (comp(con[parent],con[child]))
				{
					std::swap(con[parent], con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		//向下调整算法
		void AdiuDown(int parent)
		{
			int n = this->size();

			//找到  逻辑结构  中的左孩子节点
			int child = parent*2+1;
			while (child <n)
			{
				if (child + 1 < n && comp(con[child], con[child + 1]))
				{
					child++;
				}
				//使用  比较仿函数comp  进行比较大小
				//默认的comp是 std::less 类型的
				if (comp(con[parent], con[child]))
				{
					std::swap(con[parent], con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
	public:

		priority_queue(const Container & ctnr = Container(),const Compare & comp = Compare())
		{
			this->comp = comp;

			this->con = ctnr;

			int n = con.size();
			//建堆，从最后一个叶子节点的父亲节点开始
			//n-1为逻辑结构上的  最后一个叶子节点的下标 
			//它的父亲节点的下标等于  它的下标-1，再除以2
			for (int i = (n - 1 - 1) / 2; i >= 0; i--)
			{
				//向下调整算法
				AdiuDown(i);
			}
		}

		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			//遍历迭代器区间
			while (first != last)
			{
				//复用push进行插入
				push(*first);
				++first;
			}
		}

		size_t size()const
		{
			return con.size();
		}

		bool empty() const
		{
			return con.empty();
		}

		//堆顶的数据只支持读取，  不支持  修改
		//因为改了就有可能不是 堆 了
		//所以返回值是const T&
		const T& top() const
		{
			//堆顶的数据存储在适配器对象的第一个数据位置
			return con.front();
		}


		void push(const T& val)
		{
			//因为要把priority_queue的数据都存储在适配器对象里面
			//所以新数据，直接尾插到适配器对象里面存储
			con.push_back(val);

			//再堆新插入的数据调用向上调整算法
			//保持插入之后也还是  堆  结构
			AdiuUp(size() - 1);
		}


		void pop()
		{
			//堆不为空才能删除
			assert(!empty());

			//把堆顶与适配器最后一个数据交换
			//方便尾删
			std::swap(con[0], con[size() - 1]);

			//尾删，把原来的堆顶数据删除
			con.pop_back();

			//对换到堆顶的数据进行向下调整算法
			//保持删除之后也还是  堆  结构
			AdiuDown(0);
		}
	};
}
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
145
146
147
148
149
150