【C++】STL详解（八）—— priority_queue的使用及模拟实现&&仿函数

​

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：C++学习
🎯长路漫漫浩浩，万事皆有期待

上一篇博客：【C++】STL详解（七）—— stack和queue的使用及模拟实现

priority_queue的使用

priority_queue的介绍

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

注意： 默认情况下priority_queue是大堆。

priority_queue的定义方式

方式一： 使用vector作为底层容器，内部构造大堆结构。

priority_queue<int, vector<int>, less<int>> q1;
1

方式二： 使用vector作为底层容器，内部构造小堆结构。

priority_queue<int, vector<int>, greater<int>> q2;
1

方式三： 不指定底层容器和内部需要构造的堆结构。

priority_queue<int> q;
1

注意： 此时默认使用vector作为底层容器，内部默认构造大堆结构。

priority_queue各个接口的使用

priority_queue的各个成员函数及其功能如下：

示例：

#include 
#include 
#include 
using namespace std;
int main()
{
	priority_queue<int> q;
	q.push(3);
	q.push(6);
	q.push(0);
	q.push(2);
	q.push(9);
	q.push(8);
	q.push(1);
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl; //9 8 6 3 2 1 0
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

仿函数

仿函数/函数对象也是类，是一个类对象。类对象可以像函数一样使用。仿函数要重载operator()，我们通过代码来看一看仿函数：

namespace sherry
{
	template <class T>
	class less
	{
	public:
		bool operator()(const T& x, const T& y)const
		{
			return x < y;
		}
	};
	template <class T>
	class greater
	{
	public:
		bool operator()(const T& x, const T& y)const
		{
			return x > y;
		}
	};

}
int main()
{
	sherry::less<int> lessFunc;
	lessFunc(1, 2);
	lessFunc.operator()(1, 2);
	return 0;
}
//lessFunc是一个对象，仿函数对象，可以像函数一样使用
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

仿函数的作用在于：在C语言中我们通过传入函数指针解决升序降序问题，虽然C++兼容了C，但是C++并没有继续利用函数指针，而是通过仿函数来控制升序和降序，我们以之前写过的排序为例子，通过利用仿函数来实现升序和降序：

template<class T,class Compare>
void BubbleSort(T* a, int n, Compare com)
{
	for (int j = 0; j < n; j++)
	{
		int exchange = 0;
		for (int i = 1; i < n - j; i++)
		{
			//if (a[i]
			if (com(a[i], a[i-1]))
			{
				swap(a[i - 1], a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}
int main()
{
	sherry::less<int> lessFunc;
	sherry::greater<int> greaterFunc;
	lessFunc(1, 2);
	int a[] = { 2,3,4,5,6,1,2,8 };
    BubbleSort(a, sizeof(a) / sizeof(int),lessFunc);
	for (auto e : a)
	{
		cout << e << " ";
	}
	cout << endl;
	BubbleSort(a, sizeof(a) / sizeof(int), greaterFunc);
	for (auto e : a)
	{
		cout << e << " ";
	}
	cout << endl;

	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
42

传值传参问题：这里是直接传值传参Compare com,当然也可以传引用传参const Compare& com,不过要记得加上const进行修饰，因为一般的仿函数比较小，问题不是很大。

priority_queue的模拟实现

priority_queue的底层实际上就是堆结构，实现priority_queue之前，我们先认识两个重要的堆算法。关于堆算法的具体讲解可以看这篇博客：【树与二叉树】二叉树顺序结构实现以及堆的概念及结构

堆的向上调整算法

以大堆为例，堆的向上调整算法就是在大堆的末尾插入一个数据后，经过一系列的调整，使其仍然是一个大堆。

调整的基本思想如下：

1、将目标结点与其父结点进行比较。
2、若目标结点的值比父结点的值大，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整；若目标结点的值比其父结点的值小，则停止向上调整，此时该树已经是大堆了。

堆的向上调整算法代码：

//堆的向上调整（大堆）
void AdjustUp(vector<int>& v, int child)
{
	int parent = (child - 1) / 2; //通过child计算parent的下标
	while (child > 0)//调整到根结点的位置截止
	{
		if (v[parent] < v[child])//孩子结点的值大于父结点的值
		{
			//将父结点与孩子结点交换
			swap(v[child], v[parent]);
			//继续向上进行调整
			child = parent;
			parent = (child - 1) / 2;
		}
		else//已成堆
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

堆的向下调整算法

以大堆为例，使用堆的向下调整算法有一个前提，就是待向下调整的结点的左子树和右子树必须都为大堆。

调整的基本思想如下：

1、将目标结点与其较大的子结点进行比较。
2、若目标结点的值比其较大的子结点的值小，则交换目标结点与其较大的子结点的位置，并将原目标结点的较大子结点当作新的目标结点继续进行向下调整；若目标结点的值比其较大子结点的值大，则停止向下调整，此时该树已经是大堆了。

堆的向下调整算法代码：

//堆的向下调整（大堆）
void AdjustDown(vector<int>& v, int n, int parent)
{
	//child记录左右孩子中值较大的孩子的下标
	int child = 2 * parent + 1;//先默认其左孩子的值较大
	while (child < n)
	{
		if (child + 1 < n&&v[child] < v[child + 1])//右孩子存在并且右孩子比左孩子还大
		{
			child++;//较大的孩子改为右孩子
		}
		if (v[parent] < v[child])//左右孩子中较大孩子的值比父结点还大
		{
			//将父结点与较小的子结点交换
			swap(v[child], v[parent]);
			//继续向下进行调整
			parent = child;
			child = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}
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

模拟实现

只要知道了堆的向上调整算法和堆的向下调整算法，priority_queue的模拟实现就没什么困难了。

priority_queue的模拟实现代码：

1、基础接口

const T& top() const
{
    return _con[0];
}

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

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

2、push与向上调整

优先级队列就是堆结构，插入一个数之后，我们还需要去进行向上调整

void push(const T& x)
{
    _con.push_back(x);
    adjust_up(_con.size() - 1);
}
1
2
3
4
5

向上调整算法：

void adjust_up(size_t child)
{
    //仿函数
    Compare com;
	size_t parent = (child - 1) / 2;
	while (child > 0)
    {
        //if ( _con[parent]<_con[child])
		if (com(_con[parent], _con[child]))
        {
            swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、pop与向下调整

void pop()
{
    swap(_con[0], _con[_con.size() - 1]);
	_con.pop_back();
    adjust_down(0);
}
1
2
3
4
5
6

向下调整：

void adjust_down(size_t parent)
{
    Compare com;//仿函数
    size_t child = parent * 2 + 1;
	while (child < _con.size())
    {
        //if (child + 1 < _con.size() && _con[child] < _con[child + 1])
        if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
        {
            child++;
        }
        //if (_con[parent]<_con[child])
        if (com(_con[parent], _con[child]))
        {
            swap(_con[child], _con[parent]);
            parent = child;
            child = parent * 2 + 1;
		}
        else
        {
            break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4、构造函数

这里主要说一下迭代器区间的构造函数：自定义类型会调用自己的迭代器区间构造，所以我们并不需要一个一个push，走个初始化列表即可，同时，数据进去之后我们还要建堆，利用向下调整算法：从倒数第一个非叶子节点，既最后一个节点的父节点开始进行向下调整：

priority_queue()
{}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
    :_con(first, last)
    {
        for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
        {
            adjust_down(i);
        }
    }
1
2
3
4
5
6
7
8
9
10
11

5、总体代码

namespace sherry //防止命名冲突
{
	//比较方式（使内部结构为大堆）
	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:
		priority_queue()
		{}
		//迭代器
		template <class InputIterator>
		priority_queue(InputIterator first,InputIterator last)
		{
			while(first!=last)
			{
				_con.push_back(*first);
				++first;
			}
			for(int i=0(_con.size()-1-1)/2;i>=0;i++)
			{
				adjust_down(i);
			}
		}
		
		//堆的向上调整
		void adjust_up(int child)
		{	//logN
			int parent = (child - 1) / 2; //通过child计算parent的下标
			while (child > 0)//调整到根结点的位置截止
			{
				if (_comp(_con[parent], _con[child]))//通过所给比较方式确定是否需要交换结点位置
				{
					//将父结点与孩子结点交换
					std::swap(_con[child], _con[parent]);
					//继续向上进行调整
					child = parent;
					parent = (child - 1) / 2;
				}
				else//已成堆
				{
					break;
				}
			}
		}
		//插入元素到队尾（并排序）
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1); //将最后一个元素进行一次向上调整
		}
		//堆的向下调整
		void adjust_down(int n, int parent)
		{
			int child = 2 * parent + 1;
			//logN
			while (child < n)
			{
				if (child + 1 < n&&_comp(_con[child], _con[child + 1]))
				{
					child++;
				}
				if (_comp(_con[parent], _con[child]))//通过所给比较方式确定是否需要交换结点位置
				{
					//将父结点与孩子结点交换
					swap(_con[child], _con[parent]);
					//继续向下进行调整
					parent = child;
					child = 2 * parent + 1;
				}
				else//已成堆
				{
					break;
				}
			}
		}
		//弹出队头元素（堆顶元素）
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(_con.size(), 0); //将第0个元素进行一次向下调整
		}
		//访问队头元素（堆顶元素）
		T& top()
		{
			return _con[0];
		}
		const T& top() const
		{
			return _con[0];
		}
		//获取队列中有效元素个数
		size_t size() const
		{
			return _con.size();
		}
		//判断队列是否为空
		bool empty() const
		{
			return _con.empty();
		}
	private:
		Container _con; //底层容器
		Compare _comp; //比较方式
	};
}
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

总结：

今天我们比较详细地完成了priority_queue的使用及模拟实现，了解了一些有关的底层原理。接下来，我们将进行C++模板进阶操作的的学习。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~