【Java数据结构】堆是个什么东西？一文带你理解——优先级队列（堆）
🎄1.二叉树的顺序储存
🛸二叉树的顺序储存
🛸下标关系
🎄2.堆
🛸概念
🛸操作——向下调整（以大根堆为例，小根堆就是换个符号的事）
🛸操作——建堆
🎄3.堆的应用——优先级队列
🛸概念
🛸内部原理
🛸操作——入队列
🛸操作——出队列
🛸返回队首元素（优先级最高）
🛸Java中的优先级队列
🎄4.堆的应用——TopK问题
🎄5.堆的其他应用——堆排序
🎄1.二叉树的顺序储存
🛸二叉树的顺序储存
使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中，数组的下标位置与二叉树节点位置是一 一对应的。
- 一般只适合表示完全二叉树，因为非完全二叉树会有
空间的浪费。 - 这种方式的主要用法就是堆的表示。
🛸下标关系
已知双亲(parent)的下标，则：
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;
已知孩子（不区分左右）(child)下标，则：
双亲(parent)下标 = (child - 1) / 2;
🎄2.堆
🛸概念
- 堆 逻辑上是一棵完全二叉树
- 堆 物理上是保存在数组中
- 满足
任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆 - 反之，则是
小堆，或者小根堆，或者最小堆 - 堆的基本作用是，快速找集合中的最值
🛸操作——向下调整（以大根堆为例，小根堆就是换个符号的事）
前提：
左右子树必须已经是一个堆，才能调整。
说明：
elem 代表存储堆的数组
length 代表数组中被视为堆数据的个数（即数组有效元素个数）
parent 代表要调整子树根节点位置的下标
child 代表最小值孩子下标（如果左右都有孩子，先比较，然后使child代表最小值孩子下标）
向下调整的过程：
parent 如果已经是叶子结点，则整个调整过程结束
判断 parent 位置有没有孩子
因为堆是完全二叉树，没有左孩子就一定没有右孩子，所以先判断是否有左孩子
因为堆的存储结构是数组，所以判断是否有左孩子，即判断左孩子下标是否越界，即 若(parent×2+1) >= size 越界，再判断是否有右孩子，即若(parent×2+2) >= size 越界
确定最小孩子，比较孩子节点值，child最后储存的一定是最小孩子的下标
① 如果右孩子不存在，则 child = parent×2+1
② 否则，比较 elem[parent×2+1] 和 elem[parent×2+2] 值的大小，child储存值小的孩子的下标
比较 elem[parent] 的值 和 elem[child] 的值，如果elem[parent] <= elem[child]，则满足堆的性质，调整结束
否则，交换 elem[parent] 和 elem[child]的值
然后更新 parent 和 child 下标，即parent = child; child = 2 * parent + 1;向下重复以上过程
实现代码：
🛸操作——建堆
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。
根节点左右子树不是堆，我们怎么调整呢？这就用到上边说的向下调整
借助向下调整，就可以把一个数组构建成堆。
从倒数第一个非叶子节点开始，从后往前遍历数组，针对每个位置，依次向下调整即可。
调整前
调整后
实现代码：
🎄3.堆的应用——优先级队列
🛸概念
在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。
在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)
🛸内部原理
优先级队列的实现方式有很多，但最常见的是使用堆来构建。
🛸操作——入队列
过程（以大堆为例）：
首先按尾插方式放入数组
比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
否则，交换其和双亲位置的值，重新进行 2、3 步骤（向上调整）
直到根结点
图示：
代码实现：
🛸操作——出队列
- 为了防止破坏堆的结构，删除时
并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素 - 有效元素个数要减一，这样就相当于把队尾（
现在队尾存的是原堆顶元素）除掉了 - 然后通过向下调整方式重新调整成堆
代码实现：
🛸返回队首元素（优先级最高）
返回堆顶元素即可
🛸Java中的优先级队列
PriorityQueue implements Queue
🎄4.堆的应用——TopK问题
戳这里，我姥姥都能看懂，讲的很详细.
关键记得，找前 K 个最大的，就建 K 个大小的小堆
🎄5.堆的其他应用——堆排序
从小到大排序：先建大根堆
从大到小排序：先建小根堆
一定是先创建大堆/小堆
开始堆排序：
先交换 后调整 直到 0下标
从小到大排序 原理就是
根节点（当前树最大值）与队尾换位置，这样最大值的位置就确定了，在数组最后，end表示数组尾下标
然后end- -，再进行向下调整，使剩下的节点再变成堆，循环操作，直到end=0了，说明已经排好了
代码实现：
