STL容器——priority_queue的模拟实现

前言：priority_queue是优先队列，它满足队列的先进先出，并且每次默认出的都是优先级高的数据。默认情况下，队列顶部数据是最大值；从尾部插入数据后，会进行排序，插入的数据不一定就在尾部；排序的过程用的就是建堆，建堆的复杂度是O(log ⁿ),所以还是比较高效的。默认建立的是大堆，所以堆顶(队列顶部)的数据是最大值，出队列按照从大到小的顺序；当然也可以使其建立小堆，出队列按照从小到大的顺序，这个后面会讲到的。

---

1. priority_queue的使用

这就是priority_queue的成员函数，和栈的成员函数接口很相似。使用起来也很简单。

#include
#include
using namespace std;
int main()
{
	priority_queue<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);
	s.push(5);

	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

上面的程序，我插入了五个数据，然后查看堆顶数据，再pop掉。

结果是：5 4 3 2 1

依据我们对队列的了解，是先进先出，我先进的是 1，先出的也应该是 1。结果先出的是 5。说明优先队列对我们插入的数据进行了建堆，使得队列顶的数据是最大值。队列顶部的数据pop掉后，又会重新建堆。

我们不想建大堆，想要建立小堆也是可以实现的：

#include
#include
using namespace std;
int main()
{
	priority_queue<int, vector<int>, greater<int>> s;
	s.push(5);
	s.push(4);
	s.push(3);
	s.push(2);
	s.push(1);

	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这次我传入的是 5 4 3 2 1，我们来查看结果：

输出的是：1 2 3 4 5，说明我们建立的是小堆，堆顶的数据是最小值；这里用到了仿函数的知识，下面会讲到的。

---

2. 二叉堆的知识了解

在模拟实现priority_queue前，我们先来学习二叉堆的建立，最起码我们得知道大堆、小堆是怎样建立得。二叉堆在物理上是连续的空间，我们可以看成一个数组；在逻辑上，要看成一个完全二叉树。

2.1 二叉树的基础

比如上面的数组，物理上是连续的空间；逻辑上要看成完全二叉树；

• 父节点的下标 = (孩子节点的下标-1)/2
• 左孩子节点的下标 = 父节点的下标*2+1
• 右孩子节点的小标 = 父节点的下标*2+2

所以可以建立成这样的完全二叉树：

2.2 向下调整建堆

上面的二叉树，我们想要建成大堆该如何调整呢？可以采用向下调整的方式，从最后的孩子节点的父亲节点开始向下调整。然后依次往上，向下调整，最终就建成堆了。

   void adjustdown(int father,int *arry,int n)
   {
    //从大的子树开始向下调整
    //默认是左孩子
	int child = father * 2 + 1;
    //右孩子比左孩子大，那么从右孩子开始向下调整
	if (child + 1 < n && arry[child] < arry[child + 1])
	{
		child++;
	}
    
	while (child < n )
	{   
	    // 孩子比父亲大，交换数据，并且使父亲下标=孩子下标，向下调整
		if (arry[child] > arry[father])
		{
			swap(arry[child], arry[father]);
			father = child;
			child = father * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
   int main()
   { 
    int arry[] = { 5,4,7,8,3,2,1,9 };
	int n = sizeof(arry) / sizeof(arry[0]);

	for (int i = n; i > 0; i--)
	{
		adjustdown((i - 1 - 1) / 2, arry, n);
	}
	for (auto i : arry)
	{
		cout << i << " ";
	}
	return 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

我们可以看看结果：

很明显这是一个大堆。

---

2.3 向上调整插入数据

我们在一个堆中插入一个数据，需要向上调整，重新建堆，使这个数据能够插入堆中，又不破化堆的结构。

void adjustup(int  child,int *arry)
{
	int father = (child - 1) / 2;
	while (child > 0)
	{
		if (arry[child] > arry[father])
		{
			swap(arry[child], arry[father]);
			child = father;
			father = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

只需要传入需要向上调整的孩子节点下标，然后就可以向上调整了。

---

3.priority_queue的模拟实现

有了上面的基础，我们正式开始priority_queue的模拟实现。

#include
namespace ly
{
	template<class T,class continer=std::vector<T>>
	class priority_queue
	{
	public:
		void adjustup(size_t  child)
		{
			size_t father = (child - 1) / 2;
			while (child > 0)
			{
				if (_priority[child] > _priority[father])
				{
					std::swap(_priority[child] , _priority[father]);
					child = father;
					father = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void adjustdown(size_t father)
		{
			size_t child = father * 2 + 1;

			if (child + 1 < _priority.size() && _priority[child] < _priority[child+1])
			{
				child++;
			}

			while (child < _priority.size())
			{
				if (_priority[child] > _priority[father])
				{
					std::swap(_priority[child] , _priority[father]);
					father = child;
					child = father * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			std::swap(_priority[0], _priority[_priority.size() - 1]);
			_priority.pop_back();
			adjustdown(0);
			
		}
		const T& top() const
		{ 
			return _priority[0];
		}
		void push(const T& val)
		{
			_priority.push_back(val);
			adjustup(_priority.size()-1);
		}
		size_t size()
		{
			return _priority.size();
		}

		bool empty()
		{
			return _priority.empty();
		}
		
	private:
		continer _priority;
	};
}
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

priority_queue的模拟实现，也是利用的适配这种设计思想，但是并不是简单的封装；看代码也知道是比stack，queue复杂的。在适配的基础上，需要我自己手动的完成建堆(当然也可以用库里的)。

实现priority_queue的关键在于push()和pop(),这两个成员函数完成，其实就已经完成大部分内容了。

1. push()

思想也简单，就是尾插一个数据，再从最后一个下标向上调整。

       void push(const T& val)
		{
			_priority.push_back(val);
			adjustup(_priority.size()-1);
		}
1
2
3
4
5

2. pop()

pop()出的是堆顶，所以将头部的数据和尾部的数据先交换，再将尾部的数据pop掉，最后从头向下开始重新建堆。

       void pop()
		{
			std::swap(_priority[0], _priority[_priority.size() - 1]);
			_priority.pop_back();
			adjustdown(0);	
		}
1
2
3
4
5
6

3. 其余函数

其他的函数真的是不用咋讲，都是简单的复用，像size(),empty()都直接复用就好了。top()的话是返回头部数据，但是不能修改所以是const返回。

---

4. 仿函数

我们看到STL中实现priority_queue的模板参数有三个，上面的模拟实现只用了两个。这第三个模板参数是什么意思呢？这是个仿函数，默认传的是less，这就使得默认建大堆，如果我们显示的声明，传仿函数great，就会建立小堆。那么仿函数是什么呢？

仿函数是一个类，可以叫做仿函数类型，用仿函数实例化出的可以称为仿函数对象。其实就是一个实现函数功能的类，它必须重载operator() 运算符。仿函数大量的用于STL中，很常见，它最重要的功能就是使得函数有了类的性质。

举例：

#include
using namespace std;

struct Less
{
	bool operator() (int x,int y)
	{
		return x < y;
	}
};

int main()
{
	Less b;
	cout << b(1, 2) << endl;
	cout << b(2, 1) << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

我定义了一个类Less，我用struct定义的，它的成员函数默认权限是public，我相信这个大家都懂。重载了operator()，如果左操作数小于右操作数，那么返回1；反之返回0。

在main()中，我创建了一个仿函数对象 b。

查看结果：

这就是仿函数的基本应用，STL中priority_queue缺省的第三个模板参数是仿函数类型less<>，功能和上面的Less类似，当然要比我写的高级，高级在它的模板参数。其实也高级多少哈。

---

综上我们就理解了仿函数的作用，那么将第三个模板参数仿函数加到我们的模拟实现中，只需要改改向上调整和向下调整就行了。

namespace ly
{
	template<class T,class continer=std::vector<T>, class compare = less<T>>
	class priority_queue
	{
	public:
		void adjustup(size_t  child)
		{
			compare b;
			size_t father = (child - 1) / 2;
			while (child > 0)
			{
				if (b(_priority[father], _priority[child]))
				{
					std::swap(_priority[child] , _priority[father]);
					child = father;
					father = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void adjustdown(size_t father)
		{
			compare b;
			size_t child = father * 2 + 1;

			if (child + 1 < _priority.size() && b(_priority[father], _priority[child]))
			{
				child++;
			}

			while (child < _priority.size())
			{
				if (b(_priority[father], _priority[child]))
				{
					std::swap(_priority[child] , _priority[father]);
					father = child;
					child = father * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			std::swap(_priority[0], _priority[_priority.size() - 1]);
			_priority.pop_back();
			adjustdown(0);
			
		}
		const T& top() const
		{ 
			return _priority[0];
		}
		void push(const T& val)
		{
			_priority.push_back(val);
			adjustup(_priority.size()-1);
		}
		size_t size()
		{
			return _priority.size();
		}

		bool empty()
		{
			return _priority.empty();
		}
		
	private:
		continer _priority;
	};
}

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

那么这样就支持了仿函数的传参，所以我们如果想要建立小堆，也是可以的了。
传一个greater<>:

int main()
{
	priority_queue<int, vector<int>, greater<int>> s;
	s.push(8);
	s.push(1);
	s.push(3);
	s.push(9);
	s.push(4);

	while (!s.empty())
	{
		cout << s.top() << endl;
		s.pop();
	}

	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这样就稳了。

---

结尾语： 以上就是对priority_queue的模拟实现