STL中的优先级队列priority_queue

STL中priority_queue是一个容器适配器，本质是一个最大堆，也就是用vector实现的。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template<typename T>
class priority_queue {
public:
priority_queue() {}
virtual ~priority_queue() {}

void push(T t) {
data.push_back(t);
push_heap(data.begin(), data.end());
}
void pop() {
pop_heap(data.begin(), data.end());
data.pop_back();
}

T top() { return data.front(); }
int size() { return data.size(); }

private:
vector<T> data;
};

这是一个简单的实现，可以参考理解。STL的实现本质是一样的。

其中push_heap()和pop_heap()函数是<algorithm>中声明的，也就是STL提供的算法。使用vector中最后一个元素进行入堆，调整；出堆，调整的操作，时间复杂度为O(logn)。