Question

优先队列

Answer 1

我们知道普通队列的特点是先进先出，但是优先队列的特点则遵守以下两条规则：
- 最大优先队列：无论入队的顺序，当前最大的元素先出列。
- 最小优先队列：无论入队的顺序，当前最小的元素先出列。

说明：在学习优先队列前必须先理解 二叉堆

这时候就是 二叉堆 发挥作用的时候了。我们知道二叉堆有以下特性：
- 最大堆：堆顶是整个数组中最大的元素，且任何父节点的值都大于其子节点
- 最小堆：堆顶是整个数组中最小的元素，且任何父节点的值都小于其子节点

对于优先队列，介绍以下几种操作：
入队操作；
出队操作；
说明：以最小优先队列为例

1.入队操作
优先队列本质上就是用二叉堆来实现的，每次插入一个数据都是插入到数据数组的最后一个位置，然后再做上浮操作，如果插入的数是数组中最大数，自然会上浮到堆顶。如“图1 入队操作”所示：

2.出队操作
出队操作就是返回堆顶最小堆的数据之后用数组最后的数插入到堆顶，之后再做下沉操作。如“图2 出队操作”所示：

因为二叉堆上浮和下沉的时间复杂度都为log2(n)，所以入队和出队的时间复杂度也是log2(n)。

优先队列是基于二叉堆实现的，优先指的是按某种优先级优先出列而不是先入先出。操作系统的阻塞机制正是有优先队列实现。