Question

C++中priority_queue的基本使用

Answer 1

priority_queue是用堆实现的。堆是一种树形结构，支持用O(1)时间获取Max/Min，并且其插入和删除的时间复杂度都是log(N)。优先队列的队首元素一定是当前队列中 优先级 最高的那一个。要使用priority_queue需要 #include <queue> 并加上 using namespace std;

PS: 堆是支持用Log(N)的时间复杂度删除特定元素，而priority_queue只能删除顶点元素。为实现删除特定元素的功能，可参考以下2篇文章。
参考1
参考2

(2) 在结构体外写一个cmp结构体(本质上也是对 < 进行运算符重栽)

本质上来说， priority_queue(堆) 适用于需要不断获取元素集中 Min/Max 的场景。比如priority_queue可用于Dijkstra算法的优化，可将其从 优化至 乃至 (使用binary heap可优化至 ，Fibonacci heap可优化至 )。