priority_queue

• priority_queue叫做优先队列，其内部的元素并非按照被压入的顺序排列，而是自动根据元素的权值排列(通常权值以实数表示)。权值最高的，排在最前面
• 由于这是一个queue，因此只能从最前面取出元素，从最后面新增元素，除此之外没有其他存取元素的途径
• priority_queue缺省情况下【以vector实现的完全二叉树 + max-heap处理规则】来实现。
• 那它为什么叫做xxxx_queue呢，是因为它的接口和queue非常像，只是它的下一个元素是优先级最高的元素
• 如果同时存在若干个优先级一样的元素，那么就不能确实是哪一个会入选

声明

• 即priority_queue<Type, Container, Functional>中：
  • Type 为数据类型
  • Container为保存数据的容器，它必须是用数组实现的容器，比如vector,deque等等，但不能用 list。 STL里面默认用的是vector。
  • Functional 为元素比较方式。
    • 比较方式默认用operator<，所以如果把后面2个参数缺省的话，优先队列就是大顶堆（降序），队头元素最大。特别注意pair的比较函数。
    • 如果要用到小顶堆，则一般要把模板的3个参数都带进去。STL里面定义了一个仿函数greater<>，基本类型可以用这个仿函数声明小顶堆。

核心接口

priority_queue没有迭代器

priority_queue中的所有元素，进出都有一定的规则，只有queue顶端的元素(权值最高的元素)，才有机会被外界取用。因此priority_queue不提供遍历功能，也不提供迭代器

实现

priority_queue内部使用的是STL的heap算法