数据结构笔记总结(7.1)什么是优先队列

树这种数据结构本身在计算机科学领域占有重要的地位,不仅仅是因为二分搜索树这样一种结构,而是树这种形状本身可以产生非得多的拓展。

面对不同的问题的时候,我们可以稍微改变或限制树这种数据结构的性质,从而产生不同的数据结构,高效的解决不同的问题。

堆和优先队列

  • 普通队列:先进先出;后进后出
  • 优先队列:出队顺序和入队顺序无关;和优先级相关


具体应用:操作系统根据优先级动态选择优先级最高的任务执行


假设我们有一个任务处理中心,现在要处理若干任务请求,任务处理中心就要先找出这些请求中优先级最高的请求然后进行处理,但是在处理完这个任务的同时,很有可能又来了很多新的任务请求,这就是动态的意思。

我们不能一开始就确定任务处理中心一共需要处理多少个任务,就像在医院一样,医生并不知道每天每月或者每年要来多少患者,要随时根据新来的患者的情况调整整个队列的优先级。

随着时间的推移会不断有新的元素入队,队列中的元素是在不断变化的,所以必须使用优先队列这种数据结构来解决问题,而不仅仅是按照优先级排序。

优先队列的实现

我们把它叫优先队列,其实它本质上就是一个队列,所以之前设计的队列这个接口是完全可以复用的,大体功能其实是不变的,也是要有入队操作、出队操作、看看队首是谁、整个队列有多少个元素、队列是否为空这些接口是没有变的。

只不过对优先队列来说,实现这些接口的时候具体这些接口实现出来的功能会有区别,最大的区别其实就是在于出队以及队首元素是谁这两个操作上。

比较两种基本实现方式的入队和出队操作

数组也好,链表也好都是普通的线性结构,直接用这种普通的线性结构充当优先队列,这种情况下入队非常简单,是一种O(1)级别的操作,只是把一个新的元素扔进线性结构就好了;

但是出队不同,出队就需要扫描一遍当前整个线性结构中的所有元素,找出优先级最高的元素,把它拿出队列,由于有扫描的过程,复杂度是O(n)级别的。

另外一种方式,可以想象一下,现在问题是在出队的时候性能非常差,不能直接找到最大元素而是要扫描一下,那么有没有可能一下就知道最大的元素是谁呢?

那么我们可能会想到使用顺序线性结构,整个线性结构一直是从小到大或从大到小排列,这种情况下,出队操作就非常容易,是一个O(1)复杂度的操作,因为只需要拿出当前线性结构的队首或队尾的元素就好了。

但是此时又有一个问题了,在入队的时候是O(n)复杂度,对于每一个入队的元素都需要找到这个线性结构需要插入到队列的什么位置,最差的情况需要扫描整个线性结构的元素。

所以,这两种线性结构都不太好,这里就要引入“堆”这种数据结构了,对于入队和出队操作的时间复杂度都是O(logn)级别。

而且和之前学的二分搜素树不同,不是平均在O(logn)级别,而是在最差的情况也是O(logn)级别。这使得“堆”这种数据结构是相当高效的。

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(7.1)什么是优先队列

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多