动力节点首页 全国咨询热线:400-8080-105

绑定手机号,登录
手机号

验证码

微信登录
手机号登录
手机号

验证码

30天自动登录
微信登录与注册
微信扫码登录与注册

扫码关注微信公众号完成登录与注册
手机号登录
首页 > 文章

浅谈优先队列

06-01 17:19 399浏览
举报 T字号
  • 大字
  • 中字
  • 小字

优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优先队列ADT来完成操作,优先队列ADT是一种数据结构,它支持插入和删除最小值操作(返回并删除最小元素)或删除最大值操作(返回并删除最大元素);

这些操作等价于队列的enQueue和deQueue操作,区别在于,对于优先队列,元素进入队列的顺序可能与其被操作的顺序不同,作业调度是优先队列的一个应用实例,它根据优先级的高低而不是先到先服务的方式来进行调度;

如果最小键值元素拥有最高的优先级,那么这种优先队列叫作升序优先队列(即总是先删除最小的元素),类似的,如果最大键值元素拥有最高的优先级,那么这种优先队列叫作降序优先队列(即总是先删除最大的元素);由于这两种类型时对称的,所以只需要关注其中一种,如升序优先队列;

下面操作组成了优先队列的一个ADT;

1.优先队列的主要操作 优先队列是元素的容器,每个元素有一个相关的键值;

  • insert(key, data):插入键值为key的数据到优先队列中,元素以其key进行排序;
  • deleteMin/deleteMax:删除并返回最小/最大键值的元素;
  • getMinimum/getMaximum:返回最小/最大剑指的元素,但不删除它;

2.优先队列的辅助操作

  • 第k最小/第k最大:返回优先队列中键值为第k个最小/最大的元素;
  • 大小(size):返回优先队列中的元素个数;
  • 堆排序(Heap Sort):基于键值的优先级将优先队列中的元素进行排序;

优先队列的应用

  • 数据压缩:赫夫曼编码算法;
  • 最短路径算法:Dijkstra算法;
  • 最小生成树算法:Prim算法;
  • 事件驱动仿真:顾客排队算法;
  • 选择问题:查找第k个最小元素;
  • 等等等等....

优先队列的实现比较

实现插入删除寻找最小值无序数组1nn无序链表1nn有序数组n11有序链表n11二叉搜索树logn(平均)logn(平均)logn(平均)平衡二叉搜索树lognlognlogn二叉堆lognlogn1

当然,优先队列不是三言两语就能够马上讲完的,更多情况下需要我们结合实际的例子来进行理解,这样学习起来才会更有效率,我们也可以到动力节点在线观看免费的视频课程,对自己的学习也有很大的提升。

0人推荐
共同学习,写下你的评论
0条评论
代码小兵124
程序员代码小兵124

99篇文章贡献336699字

相关课程 更多>

作者相关文章更多>

推荐相关文章更多>

Java面试题及答案整理

代码小兵66904-21 20:01

6道经典算法面试题

杨晶珍05-12 16:39

简述Spring MVC的核心组件

代码小兵49806-11 16:26

SpringMVC 中的组件

代码小兵49806-11 16:28

Spring常见面试题

代码小兵92504-17 16:07

发评论

举报

0/150

取消