priority_queue(优先级队列的模拟使用和实现)

---

前言

今天我来讲优先级队列的内容，优先级队列的接口本质和队列是一样的，也是在队列的两端操作，唯一的区别就是
优先级队列中(默认)获得队头元素是这个序列中最小的元素。

---

正文开始

一、priority_queue的使用

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

#include//greater算法要包含的头文件
void test_priority_queue()
{
	//默认是一个大堆，默认大的优先级高 less
	//priority_queue pq;

	//变成小堆，小的优先级高怎么处理? greater
	//priority_queue, greater::value_type>> pq;
	priority_queue<int,vector<int>,greater<int>> pq;
	pq.push(3);
	pq.push(5);
	pq.push(6);
	pq.push(1);
	pq.push(4);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

class Date
{
public:
	friend ostream& operator<<(ostream& _cout, const Date& d);
	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);
	}
private:
	int _year;
	int _month;
	int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}
void TestPriorityQueue()
{
	// 大堆，需要用户在自定义类型中提供<的重载
	priority_queue<Date> q1;
	q1.push(Date(2018, 10, 29));
	q1.push(Date(2018, 10, 28));
	q1.push(Date(2018, 10, 30));
	cout << q1.top() << endl;
	// 如果要创建小堆，需要用户提供>的重载
	priority_queue<Date, vector<Date>, greater<Date>> q2;
	q2.push(Date(2018, 10, 29));
	q2.push(Date(2018, 10, 28));
	q2.push(Date(2018, 10, 30));
	cout << q2.top() << endl;
}
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

二、priority_queue的模拟实现

通过对priority_queue的底层结构了解到是一个大堆(默认)，因此只需要对堆进行封装即可。

namespace hulu
{
	template<class T>
	struct less
	{
		bool operator()(const T& l, const T& r)
		{
			return l < r;
		}
	};
	template<class T>
	struct greater
	{
		bool operator()(const T& l, const T& r)
		{
			return l > r;
		}
	};


	template<class T, class Container = vector<T>,class Compare=less<int>>
	class priority_queue
	{
	public:
		typedef typename Container::value_type VT;//类模板没有实例化，编译器就不能去类中查找
		//类模板不会留下，留下的是具体实例化模板中T以后的类
		//加了typename告诉编译器，这后面是一个类型名称，你后面实例化的类模板实例化以后再去他中找到这个value_type
		//向上调整算法
		void AdjustUp(size_t child)
		{	
			Compare com;
			while (child>0)
			{
				T parent = (child - 1) >> 1;
				//判断父亲和孩子的大小，如果父亲小就交换
				//if (_con[parent] 《 _con[child])
				if (com(_con[parent],_con[child]))
				{
					swap(_con[parent] , _con[child]);
					//迭代在判断父亲的父亲是否满足
					child = parent;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			//向上调整算法
			AdjustUp(_con.size()-1);
		}
		void AdjustDown(size_t parent)
		{
			Compare com;
			T child = parent * 2+1;
			while (child < _con.size())
			{
				// 找以parent为根的较大的孩子
				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
				{
					child += 1;
				}
				// 检测双亲是否满足情况
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			//向下调整算法
			AdjustDown(0);
		}
		T top()
		{
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
	void test_priority_queue()
	{
		hulu::priority_queue<int,vector<int>,greater<int>> pq;
		pq.push(3);
		pq.push(5);
		pq.push(6);
		pq.push(1);
		pq.push(4);
		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}
}
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

在priority_queue队列中使用到了
这个是我们写了一个类，类里面重载了()运算符，让类可以像函数一样使用,这个叫做仿函数。

类似于函数一样去使用。

可以进行指定类型的比较

比函数调用方便多了

---

(本章完)