优先级队列: 搞懂大顶堆和小顶堆 c++_优先队列小顶堆

优先级队列是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

说的比较人话一些就是：

1. 优先级队列是队列的一种，可以按照自定义的方式对队列中的数据进行排序。

方式1：大顶堆（最大的数优先级最高）

push很多数进入队列，最大的数永远在队头。如图：

 方式2：小顶堆（最小的数优先级最高）

push很多数进入队列，最小的数永远在队头。如图：

 此时，top() 获得队列中优先级最高的元素；pop() 弹出队列中优先级最高的元素

2. 优先级队列定义

priority_queue<Typename, Container, Functional>;

Typename：入队的数据类型；

Container：实现底层堆的容器，必须是数组容器，如vector，deque；

Functional：比较方式（大顶堆or小顶堆）

系统定义举例：

//小顶堆
priority_queue <int,vector<int>,greater<int>> pri_que;
//大顶堆
priority_queue <int,vector<int>,less<int>> pri_que;
//默认大顶堆
priority_queue<int> pri_que;
 

3. 自定义比较方式 

系统定义的数据类型为基本数据类型，如int，float，double等。

当数据类型(Typename)不是基本数据类型，而是自定义数据类型时，就不能用greater或less的比较方式了，而是需要自定义比较方式。

假设数据类型是一个类：student，包含姓名和成绩

class student
{
public:
   string name;
   int score;
}

若希望成绩越高，优先级越高，则定义大顶堆。定义方式如下：

自定义方式1: 重载运算符

重载 “<”

class student
{
public:
	string name;
	int score;
	friend bool operator < (student s1, student s2)
	{
		return s1.score < s2.score;
	}
};

自定义方式2: 重写仿函数

class student
{
public:
	string name;
	int score;
};
 
//大顶堆
class myComparison
{
public:
	bool operator () (student s1, student s2)
	{
		return s1.score < s2.score;
	}
};
 
//此时优先队列的定义应该如下
priority_queue<student, vector<student>, myComparison> pri_que;