算法通关村番外篇-优先队列

大家好我是苏麟 , 今天聊聊优先队列 .

优先队列

我们了解优先队列之前先说说队列 .

队列的特点是什么？ 队列的特点是先进先出（FIFO）。

入队列，将新元素置于队尾：

出队列，队头元素最先被移出：

那么，优先队列又是什么样子呢？

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

• 最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队
• 最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队

例如有一个最大优先队列，其中的最大元素是8，那么虽然8并不是队头元素， 但出队时仍然让元素8首先出队。

要实现以上需求，利用线性数据结构并非不能实现，但是时间复杂度较高。

优先队列的实现

先来回顾一下二叉堆的特性。

• 最大堆的堆顶是整个堆中的最大元素。
• 最小堆的堆顶是整个堆中的最小元素。

因此，可以用最大堆来实现最大优先队列，这样的话，每一次入队操作就是堆 的插入操作，每一次出队操作就是删除堆顶节点。 入队操作具体步骤如下。

1. 插入新节点5。

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

出队操作具体步骤如下。

1. 让原堆顶节点10出队。

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

3. 节点1“下沉”，节点9成为新堆顶。

这里的代码跟堆排序差不多 , 这里就不展示了 .

小结

• 什么是二叉堆

二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。

在最大堆中，任何一个父节点的值，都大于或等于它左、右孩子节点的值。

在最小堆中，任何一个父节点的值，都小于或等于它左、右孩子节点的值。

• 什么是优先队列

优先队列分为最大优先队列和最小优先队列。

在最大优先队列中，无论入队顺序如何，当前最大的元素都会优先出队，这是 基于最大堆实现的。

在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是 基于最小堆实现的。

这期就到这里 , 下期见!