漫画:什么是优先队列?

在之前的漫画中,我们介绍了二叉堆和堆排序。没看过的小伙伴可以看一看前文:

这一次,我们来讲一讲二叉堆的另外一个应用:优先队列

队列的特点是什么?

聪明的小伙伴们都知道,是先进先出(FIFO)

入队列:

出队列:

那么,优先队列又是什么样子呢?

优先队列不再遵循先入先出的原则,而是分为两种情况:

最大优先队列,无论入队顺序,当前最大的元素优先出队。

最小优先队列,无论入队顺序,当前最小的元素优先出队。

比如有一个最大优先队列,它的最大元素是8,那么虽然元素8并不是队首元素,但出队的时候仍然让元素8首先出队:

要满足以上需求,利用线性数据结构并非不能实现,但是时间复杂度较高,最坏时间复杂度O(n),并不是最理想的方式。

至于为什么最坏时间复杂度是O(n),大家可以思考下。

让我们回顾一下二叉堆的特性:

1.最大堆的堆顶是整个堆中的最大元素

2.最小堆的堆顶是整个堆中的最小元素

因此,我们可以用最大堆来实现最大优先队列,每一次入队操作就是堆的插入操作,每一次出队操作就是删除堆顶节点。

入队操作:

1.插入新节点5

2.新节点5上浮到合适位置。

出队操作:

1.把原堆顶节点10“出队”

2.最后一个节点1替换到堆顶位置

3.节点1下沉,节点9成为新堆顶

public class PriorityQueue {

}

代码中采用数组来存储二叉堆的元素,因此当元素超过数组范围的时候,需要进行resize来扩大数组长度。

—————END—————

●编号755,输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

人工智能与大数据技术

更多推荐《18个技术类公众微信》

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180925B0DRIM00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券