C++ STL标准库：std::priority_queue 优先队列的使用 empty() size() top() push() emplace() pop() swap()

优先队列

优先级队列是一种容器适配器，根据某种严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的一个。

此上下文类似于堆，其中元素可以随时插入，并且只能检索max heap元素（优先级队列中位于顶部的元素）。

优先级队列被实现为容器适配器，容器适配器是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素从特定容器的“背面”弹出，该容器被称为优先级队列的顶部。

底层容器可以是任何标准容器类模板或其他一些专门设计的容器类。容器应可通过随机访问迭代器访问，并支持以下操作：

• empty()
• size()
• front()
• push_back()
• pop_back()

标准容器类vector和deque满足这些要求。默认情况下，如果没有为特定优先级的队列类实例化指定容器类，则使用标准容器向量。

需要对随机访问迭代器的支持，才能始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成。

std::priority_queue::empty

函数原型：

bool empty() const;
1

测试容器是否为空

返回优先级队列是否为空：即其大小是否为零。

此成员函数有效地调用底层容器对象的member empty。

参数：
无

返回值：
如果基础容器的大小为0，则为true，否则为false。

---

std::priority_queue::size

函数原型：

size_type size() const;
1

返回priority_queue中的元素数。

该成员函数有效地调用基础容器对象的成员大小。

参数：
无

返回值：
基础容器中的元素数。

成员类型size_type是无符号整数类型。

---

std::priority_queue::top

函数原型：

const_reference top() const;
1

返回对priority_queue中顶部元素的常量引用。

最上面的元素是在priority_queue中比较高的元素，而下一个在调用priority_queue :: pop时从容器中删除的元素。

该成员函数有效地调用基础容器对象的成员前端。

参数：
无

返回值：
对priority_queue中top元素的引用。

---

std::priority_queue::push

函数原型：

void push (const value_type& val);
void push (value_type&& val);
1
2

插入元素

在priority_queue中插入一个新元素。这个新元素的内容被初始化为val。

这个成员函数有效地调用基础容器对象的成员函数push_back，然后通过在包含容器的所有元素的范围上调用push_heap算法，将其重新排序到堆中的位置。

参数：
val：
初始化插入元素的值。

成员类型值_type是容器中元素的类型(定义为第一类模板参数的别名T)。

返回值：
none

---

std::priority_queue::emplace(C++11)

函数原型：

template <class... Args> void emplace (Args&&... args);
1

构造并插入元素

向优先级队列添加新元素。这个新元素是就地构造的，传递参数作为其构造函数的参数。

此成员函数有效地调用底层容器后面的成员函数emplace_，转发参数，然后通过在包含容器所有元素的范围内调用push_heap算法将其重新排序到堆中的位置。

参数：
args:
插入的新元素

返回值：
none

---

std::priority_queue::pop

函数原型：

void pop();
1

移除priority_队列顶部的元素，有效地将其大小减小一。移除的元素是值最高的元素。

在通过调用member priority_queue:：top弹出之前，可以检索此元素的值。

此成员函数有效地调用pop_heap算法以保留优先级队列的堆属性，然后调用底层容器对象的成员函数pop_back以移除元素。

这将调用被移除元素的析构函数。

参数：
无

返回值：
无

---

std::priority_queue::swap(C++11)

函数原型：

void swap (priority_queue& x) noexcept (/*see below*/);
1

交换内容

用x的内容交换容器适配器的内容，使用相应的交换非成员函数交换底层容器值和它们的比较函数（非限定）。

此成员函数有一个noexcept说明符，该说明符与基础容器上交换操作的组合noexcept和比较函数相匹配。

参数：
x:
另一个相同类型的priority_queue容器适配器(例如，用相同的模板参数实例化，T, container和Compare)。大小可能不同。

返回值：
none

---

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <queue>

using namespace std;

void print(double& Ele)
{
	cout<<Ele<<", ";
}

template <class T>
void Out(priority_queue <T, deque<T>,less<T> >& p)
{
	 while(!p.empty())
	 {
		 cout<<p.top()<<", ";
		 p.pop();
	 }
	 cout<<endl;
}

template <class T>
void OutG(priority_queue <T, deque<T>,greater<T> >& pg)
{
	 while(!pg.empty())
	 {
		 cout<<pg.top()<<", ";
		 pg.pop();
	 }
	 cout<<endl;
}

void main()
{
	// 从小到大排序优先队列
	priority_queue <double,deque<double>,less<double> >p1,p2;
	p1.push(11.5);
	p1.push(22.5);
	p1.push(32.5);
	p1.push(21.1);
	p1.push(15.6);
	p1.push(8.9);
	p1.push(55.0);
	p2=p1;
    Out(p1);
	p1=p2;

	// 从大到小排序优先队列
	priority_queue <double,deque<double>,greater<double> >p3;
	while(p2.size())
	{
	   p3.push(p2.top());
	   p2.pop();
	}
	OutG(p3);
}
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