priority_queue优先队列

定义于头文件

queue

可能需要

vector

priority_queue

是容器适配器，它提供常数时间的（默认）最大元素查找，对数代价的插入与释出。

在

C++

中，以

int

类型为例，定义

priority_queue<int>heap;

表示的是大根堆，也即顶元素是优先队列中的最大值，但平时使用中需要使用小根堆，即顶元素是优先队列中的最小值。故需要进行比较函数的重载。

C++

提供了以下方式：

重载小于运算符

对于基本数据类型，可以使用如下方式实现大/小根堆

#include<queue>
#include<vector>
std::priority_queue<int>heap;//定义一个大根堆
std::priority_queue<int, std::vector<int>, std::greater<int>>heap;//定义一个大根堆

对于自定义基本数据类型

或者你想对基本数据类型的比较运算符进行更改，我们以二维平面上的点为例，声明相应的结构体。

#include<queue>
#include<vector>
struct Point {
	int x, y;
	Point(int _x = 0 , int _y = 0):x(_x) , y(_y){}
	bool operator < (const Point& point)const {
		return x < point.x;//以横坐标大小为优先级
	}
};
std::priority_queue<Point>heap;//定义一个大根堆

#include<queue>
#include<vector>
struct Point {
	int x, y;
	Point(int _x = 0 , int _y = 0):x(_x) , y(_y){}
	bool operator < (const Point& point)const {
		return x > point.x;//横坐标为优先级
	}
};
std::priority_queue<Point>heap;//定义一个小根堆

当然在结构体外部重载小于运算符也可以。对于

STL

库的几个常用的有序容器，一般只需要重载小于运算符就可以正常使用。

仿函数

仿函数（

functor

）又称为函数对象（

function object

）是一个能行使函数功能的类。仿函数的语法几乎和我们普通的函数调用一样，不过作为仿函数的类，都必须重载

operator()

运算符。

struct Point {
	int x, y;
	Point(int _x = 0 , int _y = 0):x(_x) , y(_y){}
};
struct Compare {
	bool operator () (const Point& a, const Point& b) {
		return a.x < b.x;
	}
};
std::priority_queue<Point, std::vector<Point>, Compare>heap;//定义一个大根堆

struct Point {
	int x, y;
	Point(int _x = 0 , int _y = 0):x(_x) , y(_y){}
};
struct Compare {
	bool operator () (const Point& a, const Point& b) {
		return a.x > b.x;
	}
};
std::priority_queue<Point, std::vector<Point>, Compare>heap;//定义一个小根堆

lambda表达式

在实际使用中，我们可能需要对于自定义类型即定义小根堆，又定义大根堆，但小于运算符只能重载一个。所以使用

lambda

表示式可以很好的解决上述问题，且更直观。

#include<queue>
#include<vector>
#include<iostream>
struct Point {
	int x, y;
	Point(int _x = 0 , int _y = 0):x(_x) , y(_y){}
};
auto Compare1 = [&](const Point& a, const Point& b)->bool {
	return a.x < b.x;
};
auto Compare2 = [&](const Point& a, const Point& b)->bool {
	return a.x > b.x;
};
//大根堆
std::priority_queue<Point, std::vector<Point>, decltype(Compare1)> heap1(Compare1);
//小根堆
std::priority_queue<Point, std::vector<Point>, decltype(Compare2)> heap2(Compare2);
int main() {
	//大根堆测试
	heap1.push({ 1 , 2 });
	heap1.push({ 4 , 3 });
	heap1.push({ 0 , 1 });
	//小根堆测试
	heap2.push({ 1 , 2 });
	heap2.push({ 4 , 3 });
	heap2.push({ 0 , 1 });
	//大根堆
	std::cout << "大根堆" << std::endl;
	while (!heap1.empty()) {
		auto [x, y] = heap1.top();
		heap1.pop();
		std::cout << x << " " << y << std::endl;
	}
	//小根堆
	std::cout << "小根堆" << std::endl;
	while (!heap2.empty()) {
		auto [x, y] = heap2.top();
		heap2.pop();
		std::cout << x << " " << y << std::endl;
	}
	return 0;
}

/*
//输出
大根堆
4 3
1 2
0 1
小根堆
0 1
1 2
4 3
*/

Java 中的优先队列

Java

中的优先队列类为

PriorityQueue

。默认是小根堆，即顶元素为优先队列中的最小的元素。对于基本数据类型，使用如下方式定义小根堆：

PriorityQueue<Integer> heap = new PriorityQueue<>();//定义小根堆

由于

Java

中没有提供运算符重载。但他提供了比较方便的

lambda

表达式更改比较方式的方法。

还是以

Integer

为例，定义大根堆：

PriorityQueue<Integer> heap = new PriorityQueue<>((a , b)->{
            return b - a;
        });//定义大根堆

注意，

Java

中的比较需要返回三个值，即小于

-1

,等于

,大于

。所以

lambda

表达式中使用减法可以减少代码的书写。

对于没有减法的基本类，如

String

，可以使用其自带的

compareTo

函数，可以按照如下实现：

PriorityQueue<String> heap = new PriorityQueue<>();//小根堆
PriorityQueue<String> heap = new PriorityQueue<>((a , b)->{
            return b.compareTo(a);
        });//大根堆

但实际还有问题，因为如果我们使用的类是

Long

，直接使用减法会导致报错。

PriorityQueue<Long> heap = new PriorityQueue<Long>((a , b)->{
           b - a;
        });//大根堆

即按照上述方式声明大根堆会出现问题，有时候在使用

Integer

时，若使用减法可能会存在溢出。故在比较明确数据范围不会产生溢出（在

Integer

范围内）可以使用减法，否则需要调用类自带的

compareTo

方法规避上述风险。即声明方式如下：

PriorityQueue<Long> heap = new PriorityQueue<>((a , b)->{
           return b.compareTo(a);
        });//大根堆

出现上述问题的原因是两个

Long

类型相减还是

Long

类型（

long

类型），而

compareTo

的结果是

Integer

类型也即

int

类型，但

Java

不支持从

long

到

int

的隐式类型转化。即：

long a = 1;
int b = a;//error
int c = (int)a;//correct