用大顶堆和小顶堆实现优先队列

大顶堆小顶堆（或大根堆小根堆）

利用大顶堆实现优先队列，所谓大顶堆，容器内部元素是有序的，而且是按从大到小排序的（小顶堆刚好相反，从小到大）。容器只有一个出口一个入口，将元素放进去之后大顶堆会自动对其进行排序，大顶堆最大的元素放在对顶（小顶堆最小元素在对顶），堆顶元素弹出后，下一个最大（或最小）的元素作堆顶。

c++的实现如下：

//构造一个空的优先队列priority_queue<int>head;//(c++默认为大顶堆)
//构造一个大顶堆priority_queue<int, vector<int>,less<int>> max_head;
//构造一个小顶堆priority_queue<int, vector<int>,greater<int>>min_head;
//第一个参数为要插入的元素类型，第二个参数为实现优先队列的底层容器，
//第三个参数为比较规则，less为大顶堆的规则，greater为小顶堆，
//系统自动实现，也可以自定义排序规则
//后两个可以省略，第一个参数不能省略自定义排序规则：
static bool cmp(const pair<int,int>& a, const pair<int,int>& b) {return a.first == b.first ? (a.second - b.second) : (a.first - b.first);
}priority_queue<pair<int,int>, vector<pair<int,int>>,cmp>pri_que;
//优先队列中存放的是一对整数，按照第一个元素升序排序，如果第一个元素相同比较第二个元素  

常见成员函数：

bool	employ() 返回值为true说明队列为空。
int	size() 返回优先队列里的元素数量。
void	pop() 删除队列顶部元素。
int	top() 返回队列顶部元素，但不删除该元素。
void	push(int value) 将元素value插入队列中。

java的实现方法：

PriorityQueue<Integer>head = new PriorityQueue<>();//注意java默认是小顶堆
//如果需要大顶堆需要自己提供比较器
class MyCmp implements Comparator<Integer>{@Overridepublic int compare(Integer o1,Integer o1) {return o2 - o1;}
}
PriorityQueue<Integer>head = new PriorityQueue<>(new MyCmp);

• • 一些常用的方法：

  • boolean	add(E e) 将指定的元素插入到此优先级队列中。
    void	clear() 从此优先级队列中删除所有元素。
    boolean	contains(Object o) 如果此队列包含指定的元素，则返回 true 。
    E	peek() 检索但不删除此队列的头，如果此队列为空，则返回 null 。
    E	poll() 检索并删除此队列的头，如果此队列为空，则返回 null 。
    boolean	remove(Object o) 从该队列中删除指定元素的单个实例（如果存在）。
    int	size() 返回此集合中的元素数。
    Object[]	toArray() 返回一个包含此队列中所有元素的数组。

总结

优先队列是一种比较重要的数据结构，可以以O(logn)的效率来增减元素，主要运用于排序。