🎄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;向下重复以上过程
实现代码：
//向下调整 public void adjustDown(int parent,int length){ int child = parent*2+1;//先找到左孩子节点 while(child<length) {//当child>=length的时候说明当前子树已经调整好了 //先根据左孩子节点判断右孩子节点是否存在，且是否大于左孩子节点 if (child + 1 < length && elem[child + 1] > elem[child]) {//如果存在,且值大于左孩子节点 child++; } //保证，child下标的数据 一定是左右孩子的最大值的下标 if (elem[child] > elem[parent]) {//如果孩子节点最大值，大于父节点，则要交换位置，因为要建大根堆 int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; //继续向下看是否符合大根堆的条件 parent = child;//更新parent下标 child = 2 * parent + 1;//更新child下标 }else{//否则不用换位置 break; } } }
🛸操作——建堆
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。
根节点左右子树不是堆，我们怎么调整呢？这就用到上边说的向下调整
借助向下调整，就可以把一个数组构建成堆。
从倒数第一个非叶子节点开始，从后往前遍历数组，针对每个位置，依次向下调整即可。
调整前
int[] array = { 1，2，3，4，5，6，7，8，9，10 };
调整后
int[] array = { 10，9，7，8，5，6，3，1，4，2 };
实现代码：
//建大堆 public void createHeap(int array[]){ //将传入的数组值存入堆的数组中 for (int i = 0; i < array.length; i++) { this.elem[i] = array[i]; this.usedSize++; } //从下往上建堆，parent 就代表每颗子树的根节点 for (int parent=(array.length-1-1)/2 ; parent>=0 ; parent--){ //对每个子树进行向下调整 //第二个参数传入有效元素个数是因为 //每次调整的结束位置应该是：this.usedSize. adjustDown(parent,this.usedSize); } }
🎄3.堆的应用——优先级队列
🛸概念
在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。
在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)
🛸内部原理
优先级队列的实现方式有很多，但最常见的是使用堆来构建。
🛸操作——入队列
过程（以大堆为例）：
- 首先按尾插方式放入
数组- 比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
- 否则，交换其和双亲位置的值，重新进行 2、3 步骤（
向上调整）- 直到根结点
图示：
代码实现：
//入堆操作 public void offer(int value){ //先判断满没满 if(isFull()){//满了要扩容 this.elem = Arrays.copyOf(this.elem,2*this.elem.length); } elem[usedSize] = value;//尾插到数组里 usedSize++;//有效值加1 adjustUp(usedSize-1);//向上调整 } //向上调整 public void adjustUp(int child){ int parent = (child-1)/2; while(child>0){ if (elem[child]>elem[parent]){//如果孩子节点大于双亲节点，换位置 int tmp = elem[parent]; elem[parent] = elem[child]; elem[child] = tmp; child = parent;//更新孩子节点位置 parent = (child-1)/2;//更新双亲点位置 }else{ break; } } } //判断是否满了 public boolean isFull(){ if (usedSize == elem.length) return true; else return false; }
🛸操作——出队列
- 为了防止破坏堆的结构，删除时
并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素 - 有效元素个数要减一，这样就相当于把队尾（
现在队尾存的是原堆顶元素）除掉了 - 然后通过向下调整方式重新调整成堆
代码实现：
//出堆操作（出根节点） public void poll() { if(isEmpty()) {//先判断是否是空堆 return; } int top = elem[0];//为了不破坏堆结构，不能直接删首元素，要先根尾部元素交换位置 elem[0] = elem[this.usedSize-1];//数组头尾交换 elem[usedSize-1] = top;//根节点元素已经来到了数组最后 usedSize--;//有效值-1，就相当于删除数组尾部元素 adjustDown(0,usedSize);//重新向下调整，使之重新变为堆 //（这时候原来的根节点已经不算了，假设原来是10个节点的堆，现在只有9个了，要做的就是将这余下的9个从头向下调整为堆） } //判断是否为空堆 public boolean isEmpty() { return this.usedSize == 0; }
🛸返回队首元素（优先级最高）
返回堆顶元素即可
//查看队首元素 public int peek() { if(isEmpty()) { throw new RuntimeException("队列为空"); } return this.elem[0]; }
🛸Java中的优先级队列
PriorityQueue implements Queue
操作 方法① 方法②
入队列 add(e) offer(e)
出队列 remove() poll()
队首元素 element() peek()
🎄4.堆的应用——TopK问题
戳这里，我姥姥都能看懂，讲的很详细.
关键记得，找前 K 个最大的，就建 K 个大小的小堆
🎄5.堆的其他应用——堆排序
从小到大排序：先建大根堆
从大到小排序：先建小根堆
一定是先创建大堆/小堆
开始堆排序：
先交换 后调整 直到 0下标
从小到大排序 原理就是
根节点（当前树最大值）与队尾换位置，这样最大值的位置就确定了，在数组最后，end表示数组尾下标
然后end- -，再进行向下调整，使剩下的节点再变成堆，循环操作，直到end=0了，说明已经排好了
代码实现：
//堆排序 public void heapSort() { int end = this.usedSize-1; while(end > 0) { int tmp = this.elem[0]; this.elem[0] =this.elem[end]; this.elem[end] = tmp; adjustDown(0,end); end--; } }
