什么是优先级队列（priority queue）？

什么是优先级队列（priority queue）？

有时候我们需要在某个元素集合中找到最小值和最大值 。

优先级队列抽象数据（Priority Queue ADT）模型是我们能够使用的方法之一，这是一种支持插入和删除最小值（DeleteMin）或者最大值（DeleteMax）的数据结构。

这两个 *** 作和队列中的进队（EnQueue）和出队（DeQueue） *** 作很相似。

区别就在于，在优先级队列中，数据进入的顺序与他们接受处理的顺序可能不同。

就像工作日程，一般是按重要程度排序而不是到来顺序。

在优先级队列中，如果最小的元素总是优先级最高（即最小元素先出列），就叫升序优先级（ascending – priority）序列。

相应的，如果最大的元素优先级最高那么就叫降序优先级（descending – priority）序列。

这两种对列具有对称性，我们只要了解一种，另一种依葫芦画瓢就可以了。

优先级队列的应用：

• 数据比较：huffman编码算法。
  

  
  

• 最短路径算法：迪刻斯彻算法。
  

  
  

• 最小生成树算法：Prim算法。
  

  
  

• 事件驱动仿真：排队的顾客。
  

  
  

• 选择问题：找到第k个最小的元素。
  

  
  

优先级队列的 *** 作：

• 插入数据（key，data）：插入带有key的数据，优先级队列中的数据的顺序由key决定。
  

  
  

• 删除最小/最大数据：移除并且返回带有最小/最大key的元素。
  

  
  

• 获取最小/最大数据：返回返回带有最小/最大key的元素（不删除）。
  

  
  

• 第k位最小/最大数据：取得第k位带有最小/最大key的元素。
  

  
  

• 取大小（Size）：返回优先级队列的大小。
  

  
  

• 堆排序：将队列中的元素按key进行排序。