在之前的漫画中,我们介绍了二叉堆和堆排序。没看过的小伙伴可以看一看前文:
这一次,我们来讲一讲二叉堆的另外一个应用:优先队列
队列的特点是什么?
聪明的小伙伴们都知道,是先进先出(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、数据库、运维等。
领取专属 10元无门槛券
私享最新 技术干货