算法(第 4 版)
Robert Sedgewick, Kevin Wayne
ACM Fellow, ACM 杰出教育家
2178 人已学习
立即订阅
登录后,你可以任选4讲全文学习
推荐试读
换一换
时长 04:02
时长 01:33:37
课程目录
已完结/共 41 讲
时长 00:58
时长 03:10
时长 05:29
时长 04:02
时长 01:24:35
时长 01:33:37
时长 01:16:16
时长 01:26:27
时长 30:28
时长 36:09
时长 48:57
时长 47:59
时长 54:43
时长 46:00
时长 56:31
时长 56:13
时长 53:55
时长 01:12:09
时长 51:36
时长 55:01
时长 01:35:07
时长 04:45
时长 04:08
时长 47:52
时长 45:42
时长 37:58
时长 01:13:26
时长 15:16
时长 17:22
时长 25:55
时长 14:40
时长 28:01
时长 04:15
时长 03:41
时长 03:52
算法(第 4 版)
15
15
1.0x
00:00/00:00
登录|注册

2.4 优先队列

许多应用程序都需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。很多情况下我们会收集一些元素,处理当前键值最大的元素,然后再收集更多的元素,再处理当前键值最大的元素,如此这般。例如,你可能有一台能够同时运行多个应用程序的电脑(或者手机)。这是通过为每个应用程序的事件分配一个优先级,并总是处理下一个优先级最高的事件来实现的。例如,绝大多数手机分配给来电的优先级都会比游戏程序的高。
在这种情况下,一个合适的数据结构应该支持两种操作:删除最大元素插入元素。这种数据类型叫做优先队列。优先队列的使用和队列(删除最老的元素)以及栈(删除最新的元素)类似,但高效地实现它则更有挑战性。
在本节中,简单地讨论优先队列的基本表现形式(其一或者两种操作都能在线性时间内完成)之后,我们会学习基于二叉堆数据结构的一种优先队列的经典实现方法,用数组保存元素并按照一定条件排序,以实现高效地(对数级别的)删除最大元素插入元素操作
优先队列的一些重要的应用场景包括模拟系统,其中事件的键即为发生的时间,而系统需要按照时间顺序处理所有事件;任务调度,其中键值对应的优先级决定了应该首先执行哪些任务;数值计算,键值代表计算错误,而我们需要按照键值指定的顺序来修正它们。在第 6 章中我们会学习一个具体的例子,展示优先队列在粒子碰撞模拟中的应用。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入介绍了优先队列及其在算法设计中的重要作用。通过优先队列,可以高效地解决从大量输入中找出最大或最小元素的问题,为处理超大输入提供了可能。文章详细介绍了基于二叉堆的优先队列实现方法,以及二叉堆的定义、表示方法和算法。此外,还介绍了多叉堆和索引优先队列的相关内容,展示了优先队列在不同场景下的灵活应用。文章还讨论了堆排序的实现过程,通过丰富的示例和详细的解释,读者可以深入理解优先队列的原理和应用。堆排序在排序复杂性的研究中有着重要的地位,因为它是唯一能够同时最优地利用空间和时间的方法。文章还回答了读者提出的关于优先队列和堆排序的疑问,为读者提供了更多的参考和理解。整体而言,本文内容涵盖了优先队列的基本概念、实现方法以及在算法设计中的应用,对读者快速了解优先队列的技术特点具有重要参考价值。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
立即购买
登录 后留言

精选留言

由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论
显示
设置
留言
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部