目录

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 堆的存储结构

我们已知堆为一棵完全二叉树，故采用顺序的方式存储在数组中。

而对于我们之前所学的二叉树，为什么没有采用顺序存储而是采用链式存储呢？

因为二叉树并非都为完全二叉树，若采用顺序存储会造成空间浪费：

因为堆采用顺序的方式进行存储，且为完全二叉树，故具有以下性质：

1. 孩子节点下标为i,则其父亲节点下标为(i - 1)/2
2. 父亲下标为i,则其左孩子下标为2i+1(2i+1<节点总数的情况下，否则无左孩子)
3. 父亲下标为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 堆的插入 

插入数据总共有两个步骤：

1. 将新元素插入堆的末尾（插入后不再为堆）
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 堆的删除

堆的删除一定删除的是堆顶元素。

故，删除元素的思想很简单，即：

1.  将堆顶元素和堆中最后一个元素交换
2.  将堆中有效数据个数（usedSize）减一
3.  对堆顶元素进行向下调整（只需要调整0下标就可以了）

 堆删除代码：

/*** 删除堆元素*/public void poll() {if (isEmpty()) {//如果堆为空，返回return;}//交换堆顶和最后一个元素swap(elem,0,usedSize-1);//堆元素有效个数-1usedSize--;//只向下调整0下标即可siftDown(0,usedSize);}

---

3.4 堆排序

若要升序排列，要建大根堆；若要降序排列，就要建小根堆。

以排升序为例：若要排升序，则为大堆，排序过程如下：

1. 将堆顶元素和堆末元素交换，有效数据个数减一（因为堆顶元素为最大值元素，此时最大值元素已来到数组末尾）
2. 将0下标处向下调整，重新调整为大堆
3. 继续将堆顶元素和堆末元素交换，有效数据个数减一（堆顶元素为次大值元素，此时次大值元素已来到数组末尾倒数二个位置处）
4. 将0下标处向下调整，重新调整为大堆
5. 重复以上过程，直至只剩一个元素的时候，此时数组已有序且为升序排列

堆排序 排升序代码 ：

/*** 堆排序*/public void heapSort() {if (isEmpty()) {return;}int end = usedSize-1;while (end > 0) {swap(elem,0,end);siftDown(0,end);end--;}}