什么是堆（优先级队列）

堆（也称为优先级队列）是一种特殊的树形数据结构。

根据根节点的值与子节点的值的大小关系，堆又分为最大堆和最小堆。

• 在最大堆中，每个节点的值总是大于或等于其任意子节点的值，因此最大堆的根节点就是整个堆的最大值。
• 在最小堆中，每个节点的值总是小于或等于其任意子节点的值，因此最小堆的根节点就是整个堆的最小值

例如，图（a）所示是一个最大堆，图（b）所示是一个最小堆。

堆通常用完全二叉树实现。在完全二叉树中，除最低层之外，其他层都被节点填满，最低层尽可能从左到右插入节点。上图中的两个堆都是完全二叉树。

完全二叉树又可以用数组实现，因此堆也可以用数组实现。如果从堆的根节点开始从上到下按层遍历，并且每层从左到右将每个节点按照 0、1、2 等的顺序编号，将编号为 0 的节点放入数组中下标为 0 的位置，编号为1的节点放入数组中下标为1的位置，以此类推就可以将堆的所有节点都添加到数组中。上图（a）中的堆可以用数组表示成下图（a）所示的形式，而上图（b）中的堆可以用数组表示成下图（b）所示的形式。

⭐ 如果数组中的一个元素的下标为 i，那么它在堆中对应节点的父节点在数组中的下标为 (i - 1) / 2，而它的左右子节点在数组中的下标分别为 2 * i + 1和 2 * i + 2。

在堆中添加元素

为了在最大堆中添加新的节点，有以下三个步骤：

1. 先从上到下、从左到右找出第 1 个空缺的位置，并将新节点添加到该空缺位置
2. 如果新节点的值比它的父节点的值大，那么交换它和它的父节点
3. 重复这个交换过程，直到新节点的值小于或等于它的父节点，或者它已经到达堆的顶部位置。

在最小堆中添加新节点的过程与此类似，唯一的不同是要确保新节点的值要大于或等于它的父节点。

所以，堆的添加操作是一个自下而上的操作。

举个例子，如果上图（a）的最大堆中添加一个新的元素 95：

• 由于节点 60 的右子节点是第1个空缺的位置，因此创建一个新的节点95并使之成为节点60的右子节点
• 此时新节点95的值大于它的父节点60的值，这违背了最大堆的定义，于是交换它和它的父节点
• 由于新节点95的值仍然大于它的父节点90的值，因此再交换新节点95和它的父节点90。此时堆已经满足最大堆的定义。

整体过程如下图：

堆的插入操作可能需要交换节点，以便把节点放到合适的位置，交换的次数最多为二叉树的深度，因此如果堆中有 n 个节点，那么它的插入操作的时间复杂度是 O(logn)。

在堆中删除元素

通常只删除位于堆顶部的元素。

以删除最大堆的顶部节点为例：

1. 将堆最低层最右边的节点移到堆的顶部
2. 如果此时它的左子节点或右子节点的值大于它，那么它和左右子节点中值较大的节点交换
3. 如果交换之后节点的值仍然小于它的子节点的值，则再次交换，直到该节点的值大于或等于它的左右子节点的值，或者到达最低层为止

删除最小堆的顶部节点的过程与此类似，唯一的不同是要确保节点的值要小于它的左右子节点的值。

所以，堆的删除操作是一个自上而下的操作。

举个例子，删除上图（a）中最大堆的顶部元素之后：

1. 将位于最低层最右边的节点60移到最大堆的顶部，如下图（c）所示
2. 此时节点60比它的左子节点80和右子节点90的值都小，因此将它和值较大的右子节点90交换，交换之后的堆如图（d）所示
3. 此时节点60大于它的左子节点30，满足最大堆的定义

堆的删除操作可能需要交换节点，以便把节点放到合适的位置，交换的次数最多为二叉树的深度，因此如果堆中有 n 个节点，那么它的删除操作的时间复杂度是 O(logn)。

Java 提供的堆实现

Java提供了类型 PriorityQueue 实现数据结构堆。

PriorityQueue在默认情况下是一个最小堆，如果使用最大堆调用构造函数就需要传入 Comparator 改变比较排序的规则。

// 构造小顶堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o1 - o2);

// 构造大顶堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);

PriorityQueue 实现了接口 Queue，它常用的函数如表所示

这就是为啥堆被称为优先级队列的原因

PriorityQueue 和其他实现接口Queue的类型一样，在某些时候调用函数add、remove和element时可能会抛出异常，但调用函数offer、poll和peek不会抛出异常。例如，如果调用函数remove从一个空堆中删除堆顶元素，就会抛出异常。但如果调用函数poll从一个空堆中删除堆顶元素，则会返回null。

⭐ 值得强调的是，虽然Java中的PriorityQueue实现了Queue接口，但它并不是一个队列，也不是按照“先入先出”的顺序删除元素的。

PriorityQueue是一个堆，每次调用函数remove或poll都将删除位于堆顶的元素。

PriorityQueue的删除顺序与元素添加的顺序无关。

同理，PriorityQueue的函数element和peek都返回位于堆顶的元素，即根据堆的类型返回值最大或最小的元素，这与元素添加的顺序无关。