优先级队列

队列是一个先进先出的线性表

优先级队列：结点之间的关系是由结点的优先级决定的，而不是由入队的先后次序决定。优先级高的先出队，优先级低的后出队

优先级队列可以基于线性结构实现

• 按照 优先级 排序
  • 入队：按照优先级插入在合适的位置 - $O(N)$
  • 出队：队头元素 - $O(1)$
• 按照 到达时间 排序
  • 入队：插入到队尾 - $O(1)$
  • 出队：寻找优先级最高的并删除 - $O(N)$

优先级队列也可以基于 二叉堆 实现

• 二叉堆指的是父子之间的大小满足一定约束的完全二叉树

  • 最小化堆：父结点的值小于等于儿子结点，也被称之为 小顶堆
  • 最大化堆：父结点的值大于等于儿子结点，也被称之为 大顶堆

• 出队：删除根结点 - $O(\log{N})$

• 入队：在最后一层的第一个空位置上添加一个元素，但添加后要调整元素的位置，以保持堆的有序性 - $O(\log{N})$

在优先队列运行的过程中，其本身结构一直为完全二叉树

# STL 中的优先级队列

头文件： <queue>

类模板： priority_queue

优先级队列的声明为 priority_queue<type,container,function>

• type: 数据类型

• container: 实现优先队列的底层容器，要求必须是以数组形式实现的容器

• function: 元素之间的比较方式

其中，第一个参数不可以省略，后两个参数可以省略

常用的成员函数：

• empty()
• size()
• top()
• pop()
• push()

参考：std::priority_queue