C++中STL容器之优先队列（堆排序）——priority_queue

admin管理员组

文章数量:1624320

文章目录

• • • • 1.优先队列的介绍
      • 2.优先队列的常用方法
      • 3. 自己定义优先级
      • • 3.1 使用结构体函数，重载运算符"()"
        • 3.2 自定义结构体，重载小于符号"<"
      • 参考资料:

1.优先队列的介绍

priority_queue 是“优先队列”。它和普通队列的区别在于，优先队列的队头元素总是最大的
——即执行 pop 操作时，删除的总是最大的元素；执行 top 操作时，返回的是最大元素的引用。即默认队列头部的元素优先级最高,所以只能访问第一个元素。

一般的优先队列结构如下图:

值得注意的是:
上图中显示元素的方式反映了它们被检索的顺序。在 容器vector 中它们也可以不像这样排序。因为默认的内部排序方式是堆排序。

优先队列的模板定义:

template < typename T, typename Container = vector <T>, typename Compare = less<T> >
class priority_queue{
    ...
};

其中，

• priority_queue 可以用 vector 和 deque 实现，默认情况下用 vector 实现；
• priority_queue 默认的元素比较器(Compare)是 less <T >。
  也就是说，在默认情况下，要放入 priority_queue 的元素必须是能用“<”运算符进行比较的，而且 priority _queue 保证以下条件总是成立：对于队头的元素 x 和任意非队头的元素 y，表达式“x<y”必为 false。但是,我们可以用第三个类型参数可以用来指定排序规则;特别的，<function>中定义了比较器 greater<T>
• 和 set/multiset 不同，priority_queue 是使用“堆排序”技术实现的，其内部并非完全有序，但却能确保最大元素总在队头。主需要在每次取走队头后对堆进行调整即可。
  因此,优先队列特别适用于“不停地在一堆元素中取走最大的元素”这种情况。
• priority_queue 队头的元素只能被查看或者修改，不能被删除。

2.优先队列的常用方法

操作	含义
push(e)	根据元素的优先级将元素置如队列，通常包含一个排序操作
top()	返回优先级队列头部优先级最高的元素的引用，但不移除
pop()	从队列中移除队首元素，但不返回
empty()	返回队列是否为空
size()	返回队列中元素的个数

注意：
队列是一种特殊的数据结构，如果想要访问全部的元素，比如列出或赋值它们，会将队列清空。但是，如果仍想保留它的元素，可以先把它赋值一份，这里可以使用一个不同类型的容器，如下面代码:

//拷贝并列出队列元素
priority_queue<string> words_copy{words}; //A copy for output
while (!words_copy.empty())
{
    cout << words_copy.top () <<" ";
    words_copy.pop();
}
cout << endl;

简单示例代码:

#include<iostream>
#include<queue>
#include<functional>
#include<string>

using namespace std;

int main()
{
	//以适当的对象来初始化一个优先级队列
	string wordsarr[] = { "one","two","three","four" }; 
	//初始化列表中的序列可以来自于任何容器，并且不需要有序。优先级队列会对它们进行排序。
	priority_queue<string> words1{ begin(wordsarr),end(wordsarr)};// "two" "three" "one" "four" 
	//拷贝对象
	priority_queue<string> copy_words;
	//也可以对容器指定反向排序greater<T>
	priority_queue<string, vector<string>,greater<string>> words2{ begin(wordsarr),end(wordsarr) }; //"four" "one" "three" "two"
	//优先级队列可以使用任何容器来保存元素，
	//只要容器有成员函数 front()、push_back()、pop_back()、size()、empty()。
	//比如deque
	priority_queue<string, deque<string>> words3{ begin(wordsarr),end(wordsarr)};

	/*常见的遍历和初始化*/
	priority_queue<double> pq1;
	pq1.push(3.2); pq1.push(9.8); pq1.push(9.8); pq1.push(5.4);
	while (!pq1.empty()) {
		cout << pq1.top() << " ";
		pq1.pop();
	} //上面输出 9.8 9.8 5.4 3.2
	cout << endl;
	priority_queue<double, vector<double>, greater<double> > pq2;
	pq2.push(3.2); pq2.push(9.8); pq2.push(9.8); pq2.push(5.4);
	while (!pq2.empty()) {
		cout << pq2.top() << " ";
		pq2.pop();
	}
	//上面输出 3.2 5.4 9.8 9.8

	system("pause");
	return 0;
}

3. 自己定义优先级

即队首元素与队中其他元素的比较都返回false。

3.1 使用结构体函数，重载运算符"()"

//定义比较结构
struct cmp1
{
	bool operator ()(int &a, int &b)
	{
		return a>b;//最小值优先
	}
};
struct cmp2
{
	bool operator ()(int &a, int &b)
	{
		return a<b;//最大值优先
	}
};

3.2 自定义结构体，重载小于符号"<"

//自定义数据结构
struct number1
{
	int x;
	bool operator < (const number1 &a) const
	{
		return x>a.x;//最小值优先
	}
};
struct number2
{
	int x;
	bool operator < (const number2 &a) const
	{
		return x<a.x;//最大值优先
	}
};

示例

#include<iostream>
#include<functional>
#include<queue>
#include<vector>
using namespace std;


int a[] = { 14,10,56,7,83,22,36,91,3,47,72,0 };
number1 num1[] = { 14,10,56,7,83,22,36,91,3,47,72,0 };
number2 num2[] = { 14,10,56,7,83,22,36,91,3,47,72,0 };

int main()
{
	priority_queue<int>que;//采用默认优先级构造队列

	priority_queue<int, vector<int>, cmp1>que1;//最小值优先
	priority_queue<int, vector<int>, cmp2>que2;//最大值优先

	priority_queue<int, vector<int>, greater<int> >que3;//注意“>>”会被认为错误，
	priority_queue<int, vector<int>, less<int> >que4;最大值优先

	priority_queue<number1>que5; //最小优先级队列
	priority_queue<number2>que6;  //最大优先级队列

	int i;
	for (i = 0; a[i]; i++)
	{
		que.push(a[i]);
		que1.push(a[i]);
		que2.push(a[i]);
		que3.push(a[i]);
		que4.push(a[i]);
	}
	for (i = 0; num1[i].x; i++)
		que5.push(num1[i]);
	for (i = 0; num2[i].x; i++)
		que6.push(num2[i]);


	printf("采用默认优先关系:\n(priority_queue<int>que;)\n");
	printf("Queue 0:\n");
	while (!que.empty())
	{
		printf("%3d", que.top());
		que.pop();
	}
	puts("");
	puts("");

	printf("采用结构体自定义优先级方式一:\n(priority_queue<int,vector<int>,cmp>que;)\n");
	printf("Queue 1:\n");
	while (!que1.empty())
	{
		printf("%3d", que1.top());
		que1.pop();
	}
	puts("");
	printf("Queue 2:\n");
	while (!que2.empty())
	{
		printf("%3d", que2.top());
		que2.pop();
	}
	puts("");
	puts("");
	printf("采用头文件functional内定义优先级:\n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)\n");
	printf("Queue 3:\n");
	while (!que3.empty()) {
		printf("%3d", que3.top());
		que3.pop();
	}
	puts("");
	printf("Queue 4:\n");
	while (!que4.empty())
	{
		printf("%3d", que4.top());
		que4.pop();
	}
	puts("");
	puts("");
	printf("采用结构体自定义优先级方式二:\n(priority_queue<number>que)\n");
	printf("Queue 5:\n");
	while (!que5.empty())
	{
		printf("%3d", que5.top());
		que5.pop();
	}
	puts("");
	printf("Queue 6:\n");
	while (!que6.empty())
	{
		printf("%3d", que6.top());
		que6.pop();
	}
	puts("");

	system("pause");
	return 0;
}

参考资料:

1.STL教程：C++ STL快速入门（非常详细）
http://c.biancheng/stl/
2.上面示例代码2转自:STL容器之优先队列
https://wwwblogs/lgh1992314/archive/2013/05/27/5835022.html

本文标签： 队列容器stlpriorityqueue