什么是优先级队列(priority queue)?

有时候我们需要在某个元素集合中找到最小值和最大值 。优先级队列抽象数据(Priority Queue ADT)模型是我们能够使用的方法之一,这是一种支持插入和删除最小值(DeleteMin)或者最大值(DeleteMax)的数据结构。

这两个操作和队列中的进队(EnQueue)和出队(DeQueue)操作很相似。区别就在于,在优先级队列中,数据进入的顺序与他们接受处理的顺序可能不同。就像工作日程,一般是按重要程度排序而不是到来顺序。

什么是优先级队列(priority queue)?

在优先级队列中,如果最小的元素总是优先级最高(即最小元素先出列),就叫升序优先级(ascending – priority)序列。相应的,如果最大的元素优先级最高那么就叫降序优先级(descending – priority)序列。这两种对列具有对称性,我们只要了解一种,另一种依葫芦画瓢就可以了。

优先级队列的应用:

  • 数据比较:huffman编码算法。
  • 最短路径算法:迪刻斯彻算法。
  • 最小生成树算法:Prim算法。
  • 事件驱动仿真:排队的顾客。
  • 选择问题:找到第k个最小的元素。

优先级队列的操作:

  • 插入数据(key,data):插入带有key的数据,优先级队列中的数据的顺序由key决定。
  • 删除最小/最大数据:移除并且返回带有最小/最大key的元素。
  • 获取最小/最大数据:返回返回带有最小/最大key的元素(不删除)。
  • 第k位最小/最大数据:取得第k位带有最小/最大key的元素。
  • 取大小(Size):返回优先级队列的大小。
  • 堆排序:将队列中的元素按key进行排序。
上一篇:在Idea创建Spring Boot + MyBatis的web项目


下一篇:高可用集群(crmsh详解)http://www.it165.net/admin/html/201404/2869.html