本文目标
带领大家掌握堆的概念以及实现
掌握PriorityQueue 的使用
二叉树的顺序存储
存储方式
使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。
这种方式的主要用法就是堆的表示。
下标关系(重要)
已知双亲(parent)的下标，则：
左孩子(left)下标 = 2 * parent + 1
右孩子(right)下标 = 2 * parent + 2
已知孩子（不区分左右）(child)下标，则：
双亲(parent)下标 = (child - 1) / 2(前提是在完全二叉树中根节点编号为0)
双亲(parent)下标 = child / 2（前提是在完全二叉树中根节点编号为1)
堆(heap)
概念
1.堆逻辑上是一棵完全二叉树
2.堆物理上是保存在数组中
3.满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
4.反之，则是小堆，或者小根堆，或者最小堆
5.堆的基本作用是，快速找集合中的最值，例如求最大值，最小值或者前k个最大/最小
操作–向下调整
此时我们想要将一个普通的堆转换成大根堆，那么该怎么转换呢？下面我们来看步骤
1:首先我们给出一个堆(本质上是一个完全二叉树)：
2:然后我们要将这个完全二叉树转换成大根堆，方法是什么呢？
这块我们需要用到向下调整，也就是从每一棵子树开始调整，每一棵子树是向下调整
那么首先我们从图中的最后这棵子树开始调整:
我们把这课小子树的父亲节点设为P,把这个父亲节点的左孩子设为C
然后找P的左右孩子的最大值，发现是37，37>28，此时就将两者进行交换：
交换完毕后此时我们四号下标这个树就已经变成大根堆了
3:此时P指向我们的三号下标处，然后C指向三号下标的左子树也就是我们的七号下标处，为什么指向这里是因为我们通过之前的下标关系公式可以得出来:也就是三号下标对应的左子树下标为2 * 3+1=7,所以此时C指向了7号下标处：
然后此时确认一下七号下标的值和八号下标的值哪个大，发现七号下标的值为49，大于八号下标的值25，所以此时应该交换七号下标的值与三号下标的值，交换后如下所示:此时C指向18，P指向49
交换后还需要判断下三号下标这棵树是否已经全部调整完毕，所以此时P仍需要再往下走，指向我们的七号下标处，也就是C原来所指向的节点，而C此时指向的下标应该为27+1=15,结果发现我们排序后才到9，所以此时我们三号下标所代表的这课子树也完成了调整.
4:此时P又往前走，指向了我们的二号下标，细心的同学会发现P其实一直都是挨个往下减，那么C此时应该指向我们的22+1=5号下标：
然后此时判断左右子树哪个大，发现五号下标值为34，六号下标值为65，所以六号下标的地方的值大，所以C此时指向六号下标处：
然后发现六号下标比我们的二号下标的值大，所以此时应该交换六号下标和二号下标的值，如下所示:此时C指向19，P指向65
判断完成后还需要判断六号下标以下的子树是否是大根堆，所以此时让P指向我们的六号下标处，也就是C原来指向的节点，然后C此时指向的下标应该为26+1=13,但是我们这棵完全二叉树下标最大才到9，所以说明以65为根节点的这个子树已经调整完毕.
5:此时P继续往前走，走到了下标为1处的节点,而我们的C此时走到了下标为12+1=3的地方，如下所示:
然后下标为3的值为49，下标为4的值为37，49>37,所以C仍指向49，然后49>15，所以将49和15进行交换：此时C指向15,P指向49
交换完毕后此时仍要检验以49为根节点的这棵子树到底是否是一个大根堆，于是将P此时指向原来C所指向的下标为3处的15这个值，然后C指向了下标为23+1=7的这个下标所对应的值18.如下所示:
此时比较P所指向的节点的左右子树的值的大小,发现25大于18，所以此时C指向了25这个节点:
然后25>15，所以将P和C所指向的节点的值进行交换:
此时继续判断当前P所指向的节点下的二叉树是否是大根堆，于是P走到了C现在的节点，然后C应该走到下标为28+1=17的节点处，结果这棵二叉树按照层序遍历排下标最大才到9，所以以25为根节点的这棵子树算是遍历完毕了.
6：此时P继续回到我们的下标为1处开始往前走，此时P走到了0下标的位置，C此时应该走到02+1=1处的位置，如下图所示：
此时65>49，所以C应该指向65这个节点，如下图所示:
又因为65>27，所以此时交换各自的值：
然后P此时指向我们C指向的节点，然后C应该指向22+1=5这个下标所对应的节点，如下所示:
34>19，所以C仍指向34这个节点，34>27，所以交换这两个值:
然后P此时继续指向C所指向的节点，因为P所指向的节点的下标为5，所以C下次指向的节点的下标应该为2*5+1=11,但是我们这棵完全二叉树的下标最大才到9，所以以65为根节点的二叉树此时调整完毕
最后我们发现我们的这棵二叉树调整完毕，已经成为了大根堆.
代码示例
废话不多说我们直接上代码，大家注意要留意我们每一行的注释，因为精髓都在这些注释里面：
/** * @author SongBiao * @Date 2021/1/18 * 此段代码用于将一个堆转变成大根堆 */ public class HeapDemo { //堆的底层存储是顺序数组 public int[] elem; //表示我们堆中的元素个数，同时也是我们堆调整时结束的标志 public int usedSize; //初始化的时候为堆的底层数组创建一个默认的大小 public HeapDemo() { this.elem = new int[10]; } /** * 注意在这里为什么要传len * 传len的目的是告诉堆调整结束时的时间，因为每颗子树在进行向下调整时最后结束的条件是一样的 * 就是当下标值大于堆中元素个数-1的时候就停止调整了 * 所以len就代表每次调整结束的位置，而我们传入的len的值其实就是usedSize * adjustDown的时间复杂度为O(log2(n)) * @param parent * @param len */ //向下调整 public void adjustDown(int parent, int len) { //获取当前根节点的左子树的下标值 int child = 2 * parent + 1; //child<len的时候说明有左子树，但是未必有右子树 while (child < len) { //注意要加上child+1<len这个操作，原因是可能会没有右孩子只有左孩子 if (child + 1 < len && this.elem[child] < this.elem[child + 1]) { child++; } //代码如果走到这里就代表child此时一定是左右孩子中的最大值所对应的下标 if (this.elem[child] > this.elem[parent]) { int tmp = this.elem[child]; this.elem[child] = this.elem[parent]; this.elem[parent] = tmp; parent = child; child = 2 * parent + 1; } else { /*因为是从最后一棵树开始调整的 只要我们 找到了 this.elem[child] <= this.elem[parent]，就说明后续就不需要循环了 后面的都已经是大根堆了，所以直接break即可*/ break; } } } //创建一个堆 //createBigHeap方法的时间复杂度为O(nlogn) //其实本质上来说建立一个大根堆和建立一个小根堆方法的时间复杂度为O(n) public void createBigHeap(int[] array) { for (int i = 0; i < array.length; i++) { this.elem[i] = array[i]; this.usedSize++; } //此处的i其实就代表了我们的图中P每次的下标 //this.usedSize - 1 - 1是为了获取我们堆中最后一棵子二叉树的父亲节点的下下标 //第一次减1是因为我们按照层序遍历拍序号的时候我们是从0开始编号的，而第二次减1是已知子节点求父节点下标的公式 //代表我们从最后一刻子树开始调整 for (int i = (this.usedSize - 1 - 1) / 2; i >= 0; i--) { adjustDown(i, this.usedSize); } } //打印我们调整后的结果 public void show() { for (int i = 0; i < usedSize ; i++) { System.out.print(this.elem[i]+ " "); } System.out.println(); } }
测试类:
public class TestDemo { public static void main(String[] args) { HeapDemo demo = new HeapDemo(); //建立我们想要调整的堆 int[] array = { 27,15,19,18,28,34,65,49,25,37}; //调整前的数组结果为[27, 15, 19, 18, 28, 34, 65, 49, 25, 37] System.out.println(Arrays.toString(array)); //创建我们的大根堆 demo.createBigHeap(array); //调整后结果为65 49 34 25 37 27 19 18 15 28 demo.show(); } }
注意事项：
1:createBigHeap方法为创建大根堆的方法，无论是创建大根堆还是小根堆的方法，其时间复杂度可以粗略估算为在循环中执行向下调整，所以为O(nlogn),但是实际上其时间复杂度为O(n),这个点建议大家直接死记硬背，至于感兴趣的朋友想知道这个O(n)怎么推出来的话，可以直接戳这个链接:
戳我进入知乎
2：adjustDown方法是我们向下调整的方法，也是我们的核心方法，即将一个堆如何编程大根堆的方法.注意这个方法有两个参数，一个是parent,一个是len,parent是将每次要调整的子树的根节点传入，而len的目的是为了作为调整结束的条件，即当child的下标大于len的值的时候就不再调整了.
最后我们向下调整的方法时间复杂度为O(logn),因为最坏的情况是从根一路比较到叶子，比较的次数为完全二叉树的高度
即时间复杂度为 O(log(n))
扩展
刚才我们是实现了将一个堆变成大根堆的方法，那么可不可以将一个堆变成小根堆呢？答案当然是可以的啦：我们只需要修改adjustDown方法即可，将里面的大于号和小于号改下即可：
先来看示意图：
public class TestDemo { public static void main(String[] args) { HeapDemo demo = new HeapDemo(); //建立我们想要调整的堆 int[] array = { 27,15,19,18,28,34,65,49,25,37}; //调整前的数组结果为[27, 15, 19, 18, 28, 34, 65, 49, 25, 37] System.out.println(Arrays.toString(array)); //创建我们的大根堆 demo.createBigHeap(array); //调整后结果为65 49 34 25 37 27 19 18 15 28 demo.show(); } }
测试类:
public class TestDemo { public static void main(String[] args) { HeapDemo demo = new HeapDemo(); //建立我们想要调整的堆 int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37}; //调整前的数组结果为[27, 15, 19, 18, 28, 34, 65, 49, 25, 37] System.out.println(Arrays.toString(array)); //创建我们的小根堆，并进行向下调整 demo.createBigHeap(array); //经历过向下调整的全新的小根堆为15 18 19 25 28 34 65 49 27 37 demo.show(); } }
