priority_C_内存溢出

priority_queue-学习笔记

- priority_queue的定义
- priority_queue容器内元素的访问
- priority_queue常用函数实例
- - push( )
  - top( )
  - pop( )
  - empty( )
  - size( )
- priority_queue内元素优先级的设置
- - 基本数据类型的优先级设置
  - 结构体类型的优先级设置
- priority_queue常见用途

priority_queue：优先队列，底层用堆来实现。

优先队列中，队首元素一定是当前队列中优先级最高的那一个。

priority_queue的定义

头文件：
#include < queue >
using namespace std;

priority_queue< typename > name;

priority_queue容器内元素的访问

与队列不同，优先队列没有front函数与back函数，只能通过top函数访问队首元素

#include 
#include 
using namespace std;
int main(){
	priority_queue<int> q;
	q.push(3);
	q.push(6);
	q.push(4);
	q.push(8);
	q.push(1);
	printf("%d\n",q.top());		//输出 8
	return 0;
}

priority_queue常用函数实例 push( )

push（x）将x入队

top( )

获得队首元素（堆顶元素）

pop( )

令队首元素出队

#include 
#include 
using namespace std;
int main(){
	priority_queue<int> q;
	q.push(3);
	q.push(6);
	q.push(4);
	q.push(8);
	q.push(1);
	printf("%d\n",q.top());		// 8
	q.pop();				//队首出队 
	printf("%d\n",q.top());		// 6
	return 0;
}

empty( )

判空

#include 
#include 
using namespace std;
int main(){
	priority_queue<int> q;
	if(q.empty()==true) printf("empty!\n");
	else	printf("not empty!\n");
	q.push(3);
	q.push(6);
	q.push(4);
	q.push(8);
	q.push(1);
	if(q.empty()==true) printf("empty!\n");
	else	printf("not empty!\n");
	printf("%d\n",q.top());	
	return 0;
}

size( )

返回队列内元素个数

#include 
#include 
using namespace std;
int main(){
	priority_queue<int> q;
	q.push(3);
	q.push(6);
	q.push(4);
	q.push(8);
	q.push(1);
	printf("%d\n",q.size()); // 5	
	return 0;
}

priority_queue内元素优先级的设置基本数据类型的优先级设置

对于int,double,char等可以直接使用的数据类型，优先级设置一般是数字大的优先级越高，因此队首元素就是优先队列内元素最大的那个，char类型的则是按字典序最大。

以下两种等价：

priority_queue<int> q;
priority_queue<int,vector<int>,less<int>> q;

其中，vector< int > 填写的是来承载底层数据结构堆（heap）的容器，如果第一个参数是double或char型，此处只需填写vector< double > 或vector< char >；
第三个参数less< int >则是对第一个参数的比较类，less< int >表示数字大的优先级越高（默认），greater< int >表示数字小的优先级越高。

因此，如果想让优先队列总是把最小的元素放在队首，只需进行如下定义：

priority_queue<int,vector<int>,greater<int>> q;

例如：

#include 
#include 
using namespace std;
int main(){
	priority_queue<int,vector<int>,greater<int> > q;
	q.push(4);
	q.push(2);
	q.push(9);
	q.push(5);
	printf("%d\n",q.top()); 	// 2
	return 0;
}

【注意】：两个> >之间加空格

结构体类型的优先级设置

如，对水果的名称和价格建立一个结构体：

struct fruit{
	string name;
	int price;
};

现希望按水果的价格高的为优先级高，就要重载小于号 "<"

struct fruit{
	string name;
	int price;
	friend bool operator < (fruit f1,fruit f2){
		return f1.price < f2.price;
	}
};

其中，friend为友元，后面的代码对fruit类型的 *** 作符<进行了重载
【注】：重载">"会编译错误，从数学上来说只需要重载小于号"<"，两种判断方法等价，而f1=f2则等价于判断 !(f1 此时就可以直接定义fruit类型的优先队列，其内部就是以价格高的水果为优先级高，如下：

priority_queue<fruit> q;

同理，如果想要价格低的水果优先级高：

struct fruit{
	string name;
	int price;
	friend bool operator < (fruit f1,fruit f2){
		return f1.price > f2.price;
	}
};

示例：

#include 
#include 
#include 
#include  
using namespace std;
struct fruit{
	string name;
	int price;
	friend bool operator < (fruit f1,fruit f2){
		return f1.price > f2.price;
	}
}f1,f2,f3;
int main(){
	priority_queue<fruit> q;	//定义一个优先队列q 
	f1.name="桃子";
	f1.price=3;
 	f2.name="苹果";
	f2.price=1;
	f3.name="芒果";
	f3.price=8;
	q.push(f1);
	q.push(f2);
	q.push(f3);
	//printf("%s %d\n",q.top().name,q.top().price); 
	//string类型必须用cout输出 
	cout<<q.top().name<<" "<<q.top().price<<endl;
	return 0;
}

优先队列的对小于号的重载函数与sort中的cmp函数的效果是相反的。

若是要将其写在结构体外面：

struct cmp{
	bool operator () (fruit f1,fruit f2){
		return f1.price>f2.price;
	}
};

此时的优先级定义：priority_queue,cmp> q;

#include 
#include 
#include 
#include  
using namespace std;
struct fruit{
	string name;
	int price;
	/*friend bool operator < (fruit f1,fruit f2){
		return f1.price > f2.price;
	}*/
}f1,f2,f3;
struct cmp{
	bool operator () (fruit f1,fruit f2){
		return f1.price>f2.price;
	}
};
int main(){
	priority_queue<fruit,vector<fruit>,cmp> q;	//定义一个优先队列q 
	f1.name="桃子";
	f1.price=3;
 	f2.name="苹果";
	f2.price=1;
	f3.name="芒果";
	f3.price=8;
	q.push(f1);
	q.push(f2);
	q.push(f3);
	//printf("%s %d\n",q.top().name,q.top().price); 
	//string类型必须用cout输出 
	cout<<q.top().name<<" "<<q.top().price<<endl;
	return 0;
}

因此，即便是基本数据类型或其他STL容器（如set），也可以通过同样的方式来定义优先级。

【注】：如果结构体内的数据较为庞大（例如出现了字符串或数组），建议使用引用来提高效率。

//结构体定义中
friend bool operator < (const fruit &f1,const fruit &f2){
	return f1.price>f2.price;
}
//单独定义cmp时
bool operator () (const fruit &f1,const fruit &f2){
	return f1.price>f2.price;
}