首页

# 优先队列

# C++

# priority_queue

priority_queue<类型,容器,排序规则> 默认是大根堆

priority_queue<int> q; // 大根堆
priority_queue<int,vector<int>,greater<int>> q; // 小根堆
priority_queue<int,vector<int>,less<int>> q; // 大根堆
struct cmp{
	bool operator() (int& a, int& b){
		return a > b;
	}
}
priority_queue<int,vector<int>,cmp> q; // 自定义的小根堆

# top()

访问堆顶

# push()

插入元素

# emplace()

使用构造函数构造对象并插入队列中

# pop()

移除队首元素

# Java

# PriorityQueue

PriorityQueue<类型> 默认是小根堆

PriorityQueue<Integer> p = new PriorityQueue<>(); // 小根堆
PriorityQueue<Integer> p = new PriorityQueue<>(Comparator.reverseOrder()); // 大根堆
class Cmp implements Comparator<int[]> {
	@Override
	public int compare(int[] a,int[] b){
		return a[1] - b[1];
	}
}
PriorityQueue<int[]> pq = new PriorityQueue<>(new Cmp());// 自定义
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (a[0] - b[0])); // 小根堆

# offer()

插入元素

# peek()

获取队首元素

# poll()

获取队首元素并删除

# Python

# heapq

Python没有直接提供优先队列，我们使用heapq库中的一些函数完成优先队列 默认是小根堆

# heapify

将list转化为堆

# heappop

heappop(heap) 获取队首并删除

# heappush

heappush(heap,item) 插入元素

# heappushpop

heappushpop(heap,item) 插入元素然后弹出队首

# heapreplace

heapreplace(heap,item) 弹出队首然后插入元素

from heapq import heappush,heappop,heappushpop,heapreplace,heapify
a = [4,3,2,1]
heapify(a) # [1,2,3,4] 小根堆（队首元素保证是最小值，其他的随机）
heappop(a) # 返回 1
heappush(a,1) # 又变回 [1,2,3,4]
heappushpop(a,1) # 弹出1 然后又插入1
heapreplace(a,1) # 插入1 然后又弹出1