目录
1、优先级队列
1.1 概念
1.2 PriorityQueue底层结构
2、 堆
2.1 堆的概念
2.2 堆的存储结构
3、优先级队列（堆）的模拟实现
3.1 堆的创建
3.1.1 向下调整算法建完整堆
3.2 堆的插入
3.2.1 向上调整算法
3.3 堆的删除
3.4 堆排序
1、优先级队列
1.1 概念
对于队列而言，数据只能从队尾进，队头出，遵循着固定的先进先出原则。
而在某些特殊场景需求下，要求优先级高的元素先出队列，
在这种情况下，数据结构应该提供两个最基本的操作：
- ①：不仅能添加新对象
- ②：还能返回最高优先级对象。
这种数据结构就是优先级队列，Java也提供了PriorityQueue集合。
1.2 PriorityQueue底层结构
PriorityQueue的底层是堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整，接下来，让我们来聊一聊堆到底是什么。
2、 堆
2.1 堆的概念
所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。
堆分为 大根堆与小根堆。
大根堆：每个节点都大于或等于其子节点。
小根堆：每个节点都小于或等于其子节点。
2.2 堆的存储结构
我们已知堆为一棵完全二叉树，故采用顺序的方式存储在数组中。
而对于我们之前所学的二叉树，为什么没有采用顺序存储而是采用链式存储呢？
因为二叉树并非都为完全二叉树，若采用顺序存储会造成空间浪费：
因为堆采用顺序的方式进行存储，且为完全二叉树，故具有以下性质：
- 孩子节点下标为i,则其父亲节点下标为(i - 1)/2
- 父亲下标为i,则其左孩子下标为2i+1(2i+1<节点总数的情况下，否则无左孩子)
- 父亲下标为i,则其右孩子下标为2i+2(2i+2<节点总数的情况下，否则无右孩子)
3、优先级队列（堆）的模拟实现
注：下文中代码实现的为大根堆
3.1 堆的创建
向下调整算法
向下调整算法：选出其左右孩子中值较小值元素（建大堆就选较大元素，建小堆就选较小元素，这里以建小堆为例），将这个元素和根节点进行比较，若比根节点还小，就和根节点交换，交换后可能导致子树不满足堆的性质，因此需要继续向下调整。
注意：向下调整算法的使用，必须要求其左右子树必须为大根堆或者小根堆！！！
向下调整算法的时间复杂度为：O（logN），因为最坏情况是从根一路比较到叶子，比较的次数即为完全二叉树的高度次。
3.1.1 向下调整算法建完整堆
我们给出一组数据：{ 27,15,19,18,28,34,65,49,25,37 }，要想将这组数据建成堆，我们可以使用向下调整法建堆。
而一组乱序数据其左右子树是不为堆的，那就需要通过向下调整算法从倒数第一个非叶子节点（下标为（数组.length-1-1)/2 ）开始建堆，直到将整棵树建成堆。
建堆的时间复杂度为：O（N）！！！，
为什么不是O（N*logN）呢？这里给出解释：
向下调整整体建堆代码：
/**
* 建堆整体时间复杂度：O（N）
*/
public void createHeap() {
//从倒数第一个飞非叶子节点开始建堆
int parent = (this.usedSize - 1 - 1)/2;
while (parent >= 0) {//O（N）
siftDown(parent,this.usedSize);
parent--;
}
}
/**
*向下调整算法
* 时间复杂度：O（logN）
* @param parent 向下调整的起始位置，即根节点
* @param usedSize 标定调整的结束 若算出的孩子节点坐标>=usedSize时，说明已调整完成
*/
private void siftDown(int parent, int usedSize) {
int child = parent*2+1;
//当没有孩子节点时，说明向下调整完成
while (child < usedSize) {
//当右孩子存在时，选出左右孩子的最大值（建大堆）
if (child + 1 < usedSize) {
if (elem[child] < elem[child + 1]) {
child = child + 1;
}
}
//和根节点进行比较
if (elem[child] > elem[parent]) {
swap(elem, parent, child);
parent = child;
child = parent*2+1;
}else {
//若根节点大，说明已是大堆，break结束
break;
}
}
}3.2 堆的插入
插入数据总共有两个步骤：
- 将新元素插入堆的末尾（插入后不再为堆）
- 使用向上调整算法调整为堆
3.2.1 向上调整算法
（这里以建小堆为例）：将元素插入到堆的末尾后，和根节点进行比较，如果比根节点还小就和根节点换，继续向上调整，直至满足堆的性质。如果没有根节点小，说明此时已满足堆的性质，调整完成。
时间复杂度：O（logN）
插入元素代码：
/**
* 插入元素
* 时间复杂度：O（logN）
* @param x：新插入元素的值
*/
public void offer(int x) {
if (isFull()) {
grow();
}
elem[usedSize] = x;
siftUp(usedSize);
usedSize++;
}
/**
* 向下调整算法
* @param childIndex：新插入元素的下标
*/
public void siftUp(int childIndex) {
//找到新节点的父节点的下标
int parent = (childIndex - 1)/2;
//parent为负数时，说明调整完成（最坏）
while (parent >= 0) {
if (elem[parent] < elem[childIndex]) {
swap(elem,parent,childIndex);
childIndex = parent;
parent = (childIndex - 1)/2;
}else {
break;
}
}
}
/**
* 如果堆底层的数组满了，就扩容
*/
private void grow() {
this.elem = Arrays.copyOf(elem,elem.length*2);
}向上调整算法建堆【拓展】
故我们也可以一个一个的插入元素（使用向上调整算法）来建堆，但是不推荐，因为时间复杂度比向下调整算法建堆要大，为：O（N*logN）
其实主要原因就是：最后一层的元素是最多的，都要一个个向上调整
3.3 堆的删除
堆的删除一定删除的是堆顶元素。
故，删除元素的思想很简单，即：
- 将堆顶元素和堆中最后一个元素交换
- 将堆中有效数据个数（usedSize）减一
- 对堆顶元素进行向下调整（只需要调整0下标就可以了）
堆删除代码：
/**
* 删除堆元素
*/
public void poll() {
if (isEmpty()) {
//如果堆为空，返回
return;
}
//交换堆顶和最后一个元素
swap(elem,0,usedSize-1);
//堆元素有效个数-1
usedSize--;
//只向下调整0下标即可
siftDown(0,usedSize);
}3.4 堆排序
若要升序排列，要建大根堆；若要降序排列，就要建小根堆。
以排升序为例：若要排升序，则为大堆，排序过程如下：
- 将堆顶元素和堆末元素交换，有效数据个数减一（因为堆顶元素为最大值元素，此时最大值元素已来到数组末尾）
- 将0下标处向下调整，重新调整为大堆
- 继续将堆顶元素和堆末元素交换，有效数据个数减一（堆顶元素为次大值元素，此时次大值元素已来到数组末尾倒数二个位置处）
- 将0下标处向下调整，重新调整为大堆
- 重复以上过程，直至只剩一个元素的时候，此时数组已有序且为升序排列
堆排序 排升序代码 ：
/**
* 堆排序
*/
public void heapSort() {
if (isEmpty()) {
return;
}
int end = usedSize-1;
while (end > 0) {
swap(elem,0,end);
siftDown(0,end);
end--;
}
}