1.优先队列和普通队列相似，但是出队按照优先级高的先出队，进队和出队时间复杂度都为O(log2n)。
2.因为内部原理是用堆实现，插入时候把堆调整（花费o(log2n)）,删除时直接删除堆顶（O(1)），然后把剩下元素调整（O(long2 n)）。把一个原始无序集合，通过完全二叉树够造成堆花费O(nlog2n)。
3.（1）.适用于动态添加和删除时，实时维护最值。(2).也可用于n个元素取前k个（比如10G的数据，取前100个最值，在内存不够情况下，只需要开辟100个数据的堆空间，把这10G数据依次读取进/出优先队列（堆）,即可解决内存的问题，而且时间复杂度在nlong2k）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
//比较优先级的方法 //1. 在队列元素的内部定义比较方法 例如： //默认 优先级/排序 struct node{ int value1, value2; friend bool operator > (const node a, const node b){ if(a.value1 == b.value1) return a.value1 < b.value1; else a.value2 == b.value2; } }; // 注意这里是升序排序, node1 < node2 < node3 // 所以优先级和顺序一样 node1 < node2 < node3 // sort() 排列后顺序为 node1 , node2 , node3 // priority_queue 按照优先级大出队, 依次出队 node3, node2, node1 ------------------------------------------------------------------------ //2. 指定 优先级/排序 //例子1 priority_queue<T, vector<T>, less<T> > q; 大顶堆, vector为指定内部实现结构。 // 注意哦：< < 之间要留空格，不然会被编译器认为 << 是一对哦 //例子2 #include <iostream> #include <queue> #include <vector> using namespace std; struct node { int value1, value2; friend bool operator < (const node &a, const node &b) { if (a.value1 != b.value1) return a.value1 < b.value1; else a.value2 < b.value2; } }; struct cmp { bool operator()(const node &a, const node &b) { if (a.value1 != b.value1) return a.value1 > b.value1; else a.value2 > b.value2; } }; int main() { priority_queue<int, vector<int>, cmp> q; } //（1）在外面指定比较用结构体,建堆方式用指定规则 //（2）外部指定比内部定义优先级高,同时出现以指定的为准 // 注意：排序是需要指定的是比较函数,优先队列指定的是比较用的结构体 // 比如 排序传 less<T>(), 优先队列传less<T> |
| c++为例 | |
|---|---|
| 初始化 | priority_queue<T> q; |
| 入队 | q.push(); |
| 出队 | q.pop(); |
| 队头( 优先队列队头是top，普通的是front ) | q.top() |
| 元素个数 | q.size(); |
| 判断队是否空 | q.empty(); |