好吧,开始累了,不想写那么多废话了,直接讲对打oj有用的部分吧。
priority_queue是由堆来实现的,底层是用vector来实现的,接收三个参数
priority_queue<int , vector<int>, less<int> >;
第一个参数是每一个结点的数据类型,第二个参数是用什么容器来构造priority_queue,第三个结点是优先级的方式(c++提供了greater<>和less<>),可以用operation来重载(类似于sort的cmp函数)
操作 | 时间复杂度 |
top() | O(1) |
push() | O(logn) |
pop() | O(logn) |
empty() | O(1) |
size() | O(1) |