STL priority_queue

priority_queue 是优先级队列，又称堆，可以存储任意类型

模板参数 T 表示存储元素的类型，Container 表示底层使用的容器，Compare 表示存储元素的比较方法(less 建大堆，greater 建小堆)

一、priority_queue 类的模拟实现

priority_queue 类常用接口模拟实现：

//test.cpp
#include "priority_queue.h"

int main()
{
	starrycat::priority_queue_test1();

	return 0;
}

//priority_queue.h
#pragma once

#include 
#include 
#include 

using std::cout;
using std::endl;

namespace starrycat
{
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y) const
		{
			return x < y;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& x, const T& y) const
		{
			return x > y;
		}
	};

	template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		void AdjustUp(size_t child)
		{
			size_t parent = (child - 1) / 2;

			while (child > 0)
			{
				if (Compare()(_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);
			AdjustUp(_con.size() - 1);
		}

		void AdjustDown(size_t parent)
		{
			size_t child = parent * 2 + 1;

			while (child < _con.size())
			{
				if (child + 1 < _con.size() && Compare()(_con[child], _con[child + 1]))
				{
					++child;
				}

				if (Compare()(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void pop()
		{
			assert(!empty());

			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}

		const T& top() const
		{
			assert(!empty());

			return _con[0];
		}

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

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

	private:
		Container _con;
	};

	void priority_queue_test1()
	{
		//priority_queue pq;
		priority_queue<int, std::vector<int>, greater<int>> pq;
		pq.push(0);
		pq.push(9);
		pq.push(6);
		pq.push(2);
		pq.push(1);
		pq.push(3);

		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
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