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