实用数据结构【优先队列】 - 优先队列详解

实用数据结构【优先队列】 - 优先队列详解

普通的队列是一种先进先出的数据结构，从队尾入队，从队头出队。在优先队列中，元素被赋予优先级，优先级高的元素先出队。

之前我们说了优先队列的实现原理，在实际的算法实现中，可以直接调用C++中的STL函数priority_queue，在Java中也提供了优先队列接口PriorityQueue。

优先队列priority_queue的成员函数如下：

• empty()：若优先队列为空，则返回真。
• pop()：出队。
• push()：入队。
• top()：取堆顶（队头），返回优先队列中优先级最高的元素。
• size()：返回优先队列中元素的个数。

优先队列的用法：

priority_queue<int , vector<int> , cmp>que;
1

其中，第1个参数为数据类型，第2个参数为容器类型，第3个参数为比较函数。后两个参数根据需要也可以省略。

priority_queue<int>que; //参数为数据类型，默认优先级【最大值优先】
1

如何控制优先队列的优先级？若不是最大值优先，则可以采用下面4种方法。

【1】 使用C++自带的库函数。首先，在头文件中引用include库函数

#include
1

functional提供了以下基于模板的比较函数对象：

• equal_to：等于。
• not_equal_to：不等于。
• greater：大于。
• greater_equal：大于或等于。
• less：小于。
• less_equal：小于或等于。

其次，创建优先队列：

priority_queue<int , vector<int> , less<int> >que1; //最大值优先
priority_queue<int , vector<int> , greater<int> >que2; //最小值优先
1
2

注意：“>>”会被认为错误，它是右移运算符，这里用空格号隔开，表示的含义不同。

【2】 自定义优先级①，队列元素为数值型：

struct cmp1{
	bool operator() (int &a , int &b) {
		return a < b; //最大值优先
	}
};

struct cmp2{
	bool operator() (int &a , int &b) {
		return a > b; //最小值优先
	}
};
1
2
3
4
5
6
7
8
9
10
11

创建优先队列：

priority_queue<int , vector<int> , cmp1> que3; //最大值优先
priority_queue<int , vector<int> , cpm2 >que4; //最小值优先
1
2

【3】 自定义优先级②，队列元素为结构体类型：

struct node1 {
	int x ,y; //结构体中的成员
	
	bool operator < (const node1 &a) const {
		return x < a.x; //最大值优先
	}
};

struct node2{
	int x , y;
	bool operator < (const node2 &a) const {
		return x > a.x; //最小值优先
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

创建优先队列：

priority_queue<node1> que5; //使用时要把数据定义为node1 类型
priority_queue<node2> que6; //使用时要把数据定义为node2 类型
1
2

【4】 自定义优先级③，队列元素为结构体类型：

struct node3{
	int x, y; //结构体中的成员
};

bool operator < (const node3 &a , const node3 &b) { //在结构体外面定义
	return a.x < b.x; //按 成员x 最大值优先
}

struct node4{
	int x, y; //结构体中的成员
};

bool operator < (const node4 &a , const node4 &b) { //在结构体外面定义
	return a.y > b.y; //按 成员y 最小值优先
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

创建优先队列：

priority_queue<node3> que7; //使用时要把数据定义为node3 类型
priority_queue<node4> que8; //使用时要把数据定义为node4 类型
1
2