优先队列、最小堆、最大堆详解
优先队列、最小堆、最大堆详解
优先队列是一种特殊的队列，支持以下两种操作：
- 插入元素：将一个元素插入到队列中。
- 取出最高优先级元素：从队列中取出具有最高优先级的元素。
堆是一种特殊的树形数据结构，它满足以下两个条件：
- 堆是一棵完全二叉树。
- 堆中的每个节点都满足堆的性质。
堆的性质分为两种：
- 最小堆：每个节点的值都小于或等于其子节点的值。
- 最大堆：每个节点的值都大于或等于其子节点的值。
优先级队列允许在任何时候访问其中具有最高优先级的元素。最小堆允许在任何时候访问其中具有最小值的元素。
堆和优先队列
在实现优先级队列时，最常用的方法是使用最小堆，可以说最小堆是优先级队列的一种实现方式。优先级队列中的元素被存储在最小堆中，其中每个元素的优先级由其值确定。这样，队列中具有最高优先级的元素就是最小堆中的根节点。每当需要访问具有最高优先级的元素时，只需访问最小堆的根节点即可。
堆的根节点就是具有最高优先级的元素——每个节点的值都小于或等于其子节点的值。
创建优先队列
Java 中的优先队列可以使用 PriorityQueue 类来创建。默认情况下，优先队列中的元素按照自然顺序进行排序，也可以通过自定义比较器来进行排序。
PriorityQueue<Integer> pq = new PriorityQueue<>();
这样创建的优先队列中，元素的类型是 Integer，元素的顺序是从小到大的。
如果要创建一个元素顺序为从大到小的优先队列，可以使用以下语句：
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b.compareTo(a));
元素的类型是 Integer，元素的顺序是从大到小的，比较器使用了一个 lambda 表达式（比较器），将元素从大到小排列。
Lambda表达式的语法是
(参数列表) -> {函数体}
PriorityQueue pq = new PriorityQueue<>(lists.length, (a, b)->(a.val - b.val));
在这里参数列表是
(a, b)
，表示比较的两个元素，函数体是
(a.val - b.val)
，表示比较的规则，即按照节点的值从小到大排序
完全二叉树与优先级队列
完全二叉树（Complete Binary Tree）是一种二叉树，其中除了最后一层，其他层的节点数都是满的，最后一层的节点都靠左对齐
1
/ \
2 3
/ \ /
4 5 6
堆与完全二叉树
堆是一种特殊的树形数据结构，它满足以下两个条件：
- 堆是一棵完全二叉树。
- 堆中的每个节点都满足堆的性质。
堆的性质分为两种：
- 最小堆：每个节点的值都小于或等于其子节点的值。
- 最大堆：每个节点的值都大于或等于其子节点的值。
下面这是一颗小顶堆：
最小堆的根节点是整个堆中的最小值。
1
/ \
2 3
/ \ / \
4 5 6 7
下面这是一颗大顶堆。
最大堆的根节点是整个堆中的最大值。
8
/ \
7 5
/ \ / \
6 4 2 1
数组转换为堆
在存储树结构时，常见的是使用数组来存放，而不需要使用指针等额外的空间。在数组中，堆的根节点存储在下标为1的位置，而其余节点按照从上到下、从左到右的顺序存储。这样，对于下标为i的节点，其左子节点的下标为2i，右子节点的下标为2i+1，而其父节点的下标为i/2。
1
/ \
2 3
/ \ / \
4 5 6 7
其实排列顺序就是从上到下，从左到右进行排列，例如{1,2,3,4,5,6,7}，看第一张图就是按照顺序进行排列，当然对照下面公式也可以来做，例如 1 的索引为0，要确定它的左子节点就是 0* 2 +1 = 1，也就是索引1，对应元素值2，同理右子节点就是 0*2+2=2，索引2也就是元素值3。
- 对于下标为i的节点：
- 左子节点的下标为2i+1
- 右子节点的下标为2i+2
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
当然上面按照顺序排列是第一步，实际上在转换为小顶堆或大顶堆，还需要进行调整。
- 向下调整（堆化）：从根结点开始，将其与两个子结点中较小者交换，直到堆的性质恢复为止。
例如假设有一个数组arr=[20, 10, 15, 30, 40]，现在要将其转化为一个小顶堆
首先，我们将数组按照完全二叉树的形式排列，在数组中堆的根节点存储在下标为1的位置，其余节点按照从上到下、从左到右的顺序存储。如下图所示：
20
/ \
10 15
/ \
30 40
从上往下、从左往右依次给每个节点编号，如下所示：
1
/ \
2 3
/ \
4 5
下面需要判断是否是小顶堆，可知根节点20并不是最小，那么需要与其子节点最小值进行交换
10
/ \
20 15
/ \
30 40
对应的数组为[10, 20, 15, 30, 40]，符合小顶堆的定义，即每个节点的值都小于或等于其子节点的值。
当然常见的笔试题中，还有出下面这样的：
最小堆删除堆顶（即根结点）元素的操作步骤：
- 删除堆顶元素：将根结点（数组第一个元素）删除；
- 用最后一个元素填补空位：把堆中最后一个元素放到根结点的位置；
- 向下调整（堆化）：从根结点开始，将其与两个子结点中较小者交换，直到堆的性质恢复为止。
0
/ \
2 1
/ \ / \
4 3 9 5
/ \ /
8 6 7
按照上面流程，由末尾元素7代替0的位置，此时判断是否是小顶堆
7
/ \
2 1
/ \ / \
4 3 9 5
/ \
8 6
依次堆化，最终结构如下：
1
/ \
2 5
/ \ / \
4 3 9 7
/ \
8 6
对应就是{1,2,5,4,3,9,7,8,6}
最小堆实现优先队列
好，我们画幅图再来理解一下。
下面我们看新增一个元素，最小堆实现的优先队列将作如何变化：
因为要维持小根堆的根节点最小，4<9 需要进行交换，4<5 需要进行交换，4>3 不需要进行交换
在优先级队列新增元素，实际上是有两个Api方法：add()和 offer()
它们都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同：
- add()在插入失败时抛出异常
- offer()会返回false
最小堆允许在任何时候访问其中具有最小值的元素。
优先级队列允许在任何时候访问其中具有最高优先级的元素。