2.2.4 优先队列和堆

1．优先队列

队列是符合“先进先出”规则的顺序表，可以应用于很多现实场景，但并不是所有的队列都是“先进先出”。比如，排队候车时，往往提示老弱病残孕者优先上车；机场候机时，VIP客户优先登机。优先队列就是处理这种非“先进先出”场景的数据结构。

优先队列是一个以集合为基础的抽象数据结构，其中每个元素都有一个优先值，它可以是一个实数，也可以是一个一般全序集中的元素。优先值用来表示该元素出列的优先级。本章约定优先值小的优先级高，当然也可以约定优先值大的优先级高。

定义在优先队列上的基本运算包括：

☢ top()运算——返回优先队列中具有最高优先级的元素。

☢ push()运算——把某个元素插入优先队列中合适位置。

☢ pop()运算——删除优先队列中具有最高优先级的元素。

top()和pop()运算只关注优先级最高的元素；push()运算不要求维持队列的全局序关系。基于这些性质，人们提出了优先级树。优先级树是满足下面的优先性质的二叉树：树中每个结点存储一个元素，任意结点中存储元素的优先级不低于其儿子结点中存储的元素的优先级。

显然，优先级树的根结点中存储的元素具有最高优先级。从根到叶的任一条路径上，各结点中元素按优先级的非增序排列。

从优先级树的定义可以推导出，表示同一优先队列的优先级树不是唯一的。由于在优先级树中执行push()和pop()运算所需的时间与树高有关，因此用平衡的优先级树表示优先队列是一个好的选择。下面介绍一种特殊的优先级树——堆。

2．二叉堆

如果一棵优先级树是一棵完全二叉树，那么这棵具有优先级性质的完全二叉树（外形像堆）就被称为二叉堆。如2.2.3节所述，完全二叉树可以用顺序存储结构表示，因此二叉堆一般用顺序线性表（数组）来实现。

给定一个关键码序列{k₀,k₁,⋅⋅⋅,k_n−1}，如果满足k_i≥k₂i+1，k_i≥k₂i+2(i=0, 1, …, n/2-1)则称其为大根堆；如果满足小于等于关系，则为小根堆，如图2-21所示。

图2-21 小根堆和大根堆

在二叉堆中，top()操作为获取序列第一个元素，其时间复杂度为O(1)。pop()和push()操作的时间复杂度为O(log(n))。算法实现细节参阅文献[1]。

STL的priority_queue类提供了优先队列的实现，还提供了实现堆的泛型函数，见2.3节。