c++ priority_queues

1
2
3
4
5
6
7
priority_queue 优先级队列是一个拥有权值概念的单向队列queue，在这个队列中，所有元素是按优先级排列的（也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素优先权要高于后进入队列的元素）。在计算机操作系统中，优先级队列的使用是相当频繁的，进线程调度都会用到。在STL的具体实现中，priority_queue也是以别的容器作为底部结构，再根据堆的处理规则来调整元素之间的位置

empty	判断是否为空
size	返回元素的数量
top	返回位于顶部的引用的元素
push	将一个元素添加到顶部
pop	删除顶部的元素

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
#include <queue>
#include <vector>
#include <deque>
#include <list>
#include <xfunctional>
#include <iostream>

//构造函数
void priority_queueConstructor(void);

//从priority_queue中删除顶部的元素
void priority_queue_pop(void);

//将一个元素添加到priority_queue的顶部 
void priority_queue_push(void);

//返回priority_queue元素的数量 
void priority_queue_size(void);

//返回位于priority_queue顶部的引用的元素 
void priority_queue_top(void);

int main()
{
	//priority_queueConstructor();
	//priority_queue_pop();
	//priority_queue_push();
	//priority_queue_size();
	//priority_queue_top();
	using namespace std;
	priority_queue <int> q1;
	q1.push(1);
	q1.push(2);
	q1.push(3);
	q1.push(4);
	q1.push(5);
	return 0;
}


//构造函数
void priority_queueConstructor(void)
{
	using namespace std;

	// The first member function declares priority_queue
	// with a default vector base container
	priority_queue <int> q1;
	cout << "q1 = ( ";
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << ")" << endl;

	// Explicitly declares a priority_queue with nondefault
	// deque base container
	priority_queue <int, deque <int> > q2;
	q2.push(5);
	q2.push(15);
	q2.push(10);
	cout << "q2 = ( ";
	while (!q2.empty())
	{
		cout << q2.top() << " ";
		q2.pop();
	}
	cout << ")" << endl;

	// This method of printing out the elements of a priority_queue
	// removes the elements from the priority queue, leaving it empty
	cout << "After printing, q2 has " << q2.size() << " elements." << endl;

	// The third member function declares a priority_queue 
	// with a vector base container and specifies that the comparison 
	// function greater is to be used for ordering elements
	priority_queue <int, vector<int>, greater<int> > q3;
	q3.push(2);
	q3.push(1);
	q3.push(3);
	cout << "q3 = ( ";
	while (!q3.empty())
	{
		cout << q3.top() << " ";
		q3.pop();
	}
	cout << ")" << endl;

	// The fourth member function declares a priority_queue and
	// initializes it with elements copied from another container:
	// first, inserting elements into q1, then copying q1 elements into q4
	q1.push(100);
	q1.push(200);
	priority_queue <int> q4(q1);
	cout << "q4 = ( ";
	while (!q4.empty())
	{
		cout << q4.top() << " ";
		q4.pop();
	}
	cout << ")" << endl;

	// Creates an auxiliary vector object v5 to be used to initialize q5
	vector <int> v5;
	vector <int>::iterator v5_Iter;
	v5.push_back(10);
	v5.push_back(30);
	v5.push_back(20);
	cout << "v5 = ( ";
	for (v5_Iter = v5.begin(); v5_Iter != v5.end(); v5_Iter++)
		cout << *v5_Iter << " ";
	cout << ")" << endl;

	// The fifth member function declares and
	// initializes a priority_queue q5 by copying the
	// range v5[_First, _Last) from vector v5
	priority_queue <int> q5(v5.begin(), v5.begin() + 2);
	cout << "q5 = ( ";
	while (!q5.empty())
	{
		cout << q5.top() << " ";
		q5.pop();
	}
	cout << ")" << endl;

	// The sixth member function declares a priority_queue q6
	// with a comparison function greater and initializes q6
	// by copying the range v5[_First, _Last) from vector v5
	priority_queue <int, vector<int>, greater<int> >
		q6(v5.begin(), v5.begin() + 2);
	cout << "q6 = ( ";
	while (!q6.empty())
	{
		cout << q6.top() << " ";
		q6.pop();
	}
	cout << ")" << endl;

	return;
	/*
	q1 = ( )
	q2 = ( 15 10 5 )
	After printing, q2 has 0 elements.
	q3 = ( 1 2 3 )
	q4 = ( 200 100 )
	v5 = ( 10 30 20 )
	q5 = ( 30 10 )
	q6 = ( 10 30 )
	请按任意键继续. . .
	*/

}

//从priority_queue中删除顶部的元素
void priority_queue_pop(void)
{
	using namespace std;
	priority_queue <int> q1, s2;

	q1.push(10);
	q1.push(20);
	q1.push(30);

	priority_queue <int>::size_type i, iii;
	i = q1.size();
	cout << "The priority_queue length is " << i << "." << endl;

	const int& ii = q1.top();
	cout << "The element at the top of the priority_queue is "
		<< i << "." << endl;

	q1.pop();

	iii = q1.size();
	cout << "After a pop, the priority_queue length is "
		<< iii << "." << endl;

	const int& iv = q1.top();
	cout << "After a pop, the element at the top of the "
		<< "priority_queue is " << iv << "." << endl;

	return;
	/*
	The priority_queue length is 3.
	The element at the top of the priority_queue is 3.
	After a pop, the priority_queue length is 2.
	After a pop, the element at the top of the priority_queue is 20.
	请按任意键继续. . .
	*/
}

//将一个元素添加到priority_queue的顶部 
void priority_queue_push(void)
{
	using namespace std;
	priority_queue<int> q1;

	q1.push(10);
	q1.push(30);
	q1.push(20);

	priority_queue<int>::size_type i;
	i = q1.size();
	cout << "The priority_queue length is " << i << "." << endl;

	const int& ii = q1.top();
	cout << "The element at the top of the priority_queue is "
		<< ii << "." << endl;

	return;
	/*
	The priority_queue length is 3.
	The element at the top of the priority_queue is 30.
	请按任意键继续. . .
	*/
}

//返回priority_queue元素的数量 
void priority_queue_size(void)
{
	using namespace std;
	priority_queue <int> q1, q2;
	priority_queue <int>::size_type i;

	q1.push(1);
	i = q1.size();
	cout << "The priority_queue length is " << i << "." << endl;

	q1.push(2);
	i = q1.size();
	cout << "The priority_queue length is now " << i << "." << endl;

	return;
	/*
	The priority_queue length is 1.
	The priority_queue length is now 2.
	请按任意键继续. . .
	*/
}

//返回位于priority_queue顶部的引用的元素 
void priority_queue_top(void)
{
	using namespace std;
	priority_queue<int> q1;

	q1.push(10);
	q1.push(30);
	q1.push(20);

	priority_queue<int>::size_type i;
	i = q1.size();
	cout << "The priority_queue length is " << i << "." << endl;

	const int& ii = q1.top();
	cout << "The element at the top of the priority_queue is "
		<< ii << "." << endl;

	return;
	/*
	The priority_queue length is 3.
	The element at the top of the priority_queue is 30.
	请按任意键继续. . .
	*/
}