STL在算法设计中的应用——优先队列作为堆

优先队列作为堆

STL在算法设计中的应用有如下几种：
Ⅰ.存放主数据
Ⅱ.存放临时数据
Ⅲ.检测数据元素的唯一性
Ⅳ.数据的排序
⭐Ⅴ.优先队列作为堆
此篇主要内容就是 Ⅴ.优先队列作为堆

在有些算法设计中用到堆，堆采用STL的优先队列来实现，优先级的高低由队列中数据元素（比较运算符）确定，很多情况下需要重载关系函数。

一、元素为内置类型的堆

①对于C/C++内置数据类型，默认是以less<T>(小于关系函数）作为关系函数，值越大优先级越高（即大根堆），可以改为greater<T>作为关系函数，这样值越大优先级越低（即小根堆）。
②例如，以下程序中pq1为大根堆（默认），pq2为小根堆。

#include<iostream>
#include<queue>
using namespace std;
int main(){
	int a[]={3,6,1,5,4,2};
	int n=sizeof(a)/sizeof(a[0]);
	//优先级队列pq1默认使用vector作为容器 
	priority_queue<int> pq1(a,a+n); 
	cout<<"pq1：";
	while(!pq1.empty())
	{
		cout<<pq1.top()<<" ";
		pq1.pop();
	 } 
	 cout<<endl;
	 //优先级队列pq2默认使用vector作为容器 ,int元素的关系函数改为greater 
	 priority_queue<int,vector<int>,greater<int> > pq2(a,a+n); 
	 cout<<"pq2：";
	 while(!pq2.empty())
	{
		cout<<pq2.top()<<" ";
		pq2.pop();
	 } 
	 cout<<endl;
	return 0;
} 

执行结果：

pq1：6 5 4 3 2 1
pq2：1 2 3 4 5 6

二、元素为自定义类型的堆

①对于自定义数据类型（如结构体数据），同样默认以less<T>(小于关系函数）作为关系函数，但是需要重载该函数。另外用户可以自己定义关系函数，在这些重载函数或者关系函数中指定数据的优先级（优先级取决于哪些结构体，hhi越大越优先还是越小越优先）。
②实现优先队列主要有以下三种方式：
♥方式1：在声明结构体类型中重载<运算符，以指定优先级，例如priority_queuepq1调用默认的<运算符创建堆pq1（是大根堆还是小根堆由<重载函数体确定）
♥方式2：在声明结构体类型中重载>运算符，以指定优先级，例如priority_queue<Stud,greater>pq1,调用重载的>运算符创建堆pq2此时需要指定优先队列的底层容器（这里是vector也可以是deque）
♥方式3：自己定义关系函数，以指定优先级，例如priority_queue<Stud,vector,StudCmp>pq3,调用StudCmp()运算符创建堆pq3此时需要指定优先队列的底层容器（这里是vector也可以是deque）

②例如，以下程序采用上述三种方式分别创建3个堆

#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct Stud{
	int no;
	string name;
	Stud(int no1,string name1)//构造函数
	{
		no=no1;
		name=name1;
	 } 
	 bool operator<(const Stud &s) const //方式1：重载<运算符
	 {
	 	return no<s.no;
	  } 
	   bool operator>(const Stud &s) const //方式1：重载<运算符
	 {
	 	return no>s.no;
	  } 
}; 
struct StudCmp{//方式2：定义关系函数 
	 bool operator()(const Stud &s,const Stud &t) const {
	 return s.name<t.name;
	 }
}; 
void dis(vector<Stud> &myv)
{
	vector<Stud>::iterator it;
	for(it=myv.begin();it!=myv.end();it++)
	cout<<it->no<<","<<it->name<<"\t";
	cout<<endl;
}
int main(){
	Stud a[]={Stud(2,"Mary"),Stud(1,"John"),Stud(5,"Smith")};
	int n=sizeof(a)/sizeof(a[0]);
	//用Stud结构体的<关系函数定义pq1 
	priority_queue<Stud> pq1(a,a+n); 
	cout<<"pq1出队顺序：";
	while(!pq1.empty())
	{
		cout<<"["<<pq1.top().no<<","<<pq1.top().name<<"]\t";
		pq1.pop();
	 } 
	 cout<<endl;
	 //用Stud结构体的>关系函数定义pq2
	 priority_queue<Stud,deque<Stud>,greater<Stud> > pq2(a,a+n); 
	 cout<<"pq2出队顺序：";
	 while(!pq2.empty())
	{
		cout<<"["<<pq2.top().no<<","<<pq2.top().name<<"]\t";
		pq2.pop();
	 } 
	 cout<<endl;
	 //使用结构体StudCmp的关系函数定义pq3
	   priority_queue<Stud,deque<Stud>,StudCmp> pq3(a,a+n); 
	   cout<<"pq3出队顺序：";
	 while(!pq3.empty())
	{
		cout<<"["<<pq3.top().no<<","<<pq3.top().name<<"]\t";
		pq3.pop();
	 } 
	 cout<<endl;
	return 0;
} 

执行结果：

pq1出队顺序：[5,Smith]  [2,Mary]        [1,John]
pq2出队顺序：[1,John]   [2,Mary]        [5,Smith]
pq3出队顺序：[5,Smith]  [2,Mary]        [1,John]