1，基础知识
1）完全二叉树，双亲节点和孩子节点的关系
array[0，...，n-1]表示完全二叉树顺序存储模式
1.节点array[i] 的父节点为 i==0 ? null : array[i-1/2]
2.节点array[i]的左孩子为，array[2*i + 1]
3.节点array[i]的右孩子为，array[2*i + 2]
2）堆在数组中的表示方式
堆的逻辑结构是一颗完全二叉树，存储结构是一个数组。
数组为完全二叉树的层次遍历的结果。
3）大根堆和小根堆的定义
前提0 <= i < (n-1)/2
1.满足array[i] <= array[2i + 1] && array[i] <= array[2i + 2] 为小根堆。
2.满足array[i] >= array[2i + 1] && array[i] >= array[2i + 2] 为大根堆。
2，创建小根堆
1）调整数组为小根堆
处理非叶子节点顺序从[len/2 -1 ~ 0]
调整小根堆顺序，从上往下调整
image.png
2）小根堆插入
将元素放到数组末尾
和parent比较，从下往上调整小根堆
image.png
3）小根堆删除
删除array[0] -> array[0] = array[size-1] -> array[size-1] = 0
从上往下，父节点与左右孩子的最小值比较，依次调整小根堆
image.png
image.png
3，大根堆
1）调整方法。
父节点与左右子节点的最大者比较，如果小于max，则交换。
image.png
2）大根堆插入
放入数组的最后一个位置
节点上浮，与父节点(i-1)/2比较
3）大根堆删除
删除堆顶元素 -> 将最后个元素赋值给堆顶
从上往下，父节点与左右子孩子的最大值比较，调整最大堆。
4）JDK实现大根堆和小跟堆
PriorityQueue：默认为小根堆
PriorityQueue：自定义的Comparator，使用o2 - o1，实现大根堆
4，堆排序
1）一种选择排序，最坏、最好、平均负责度都为nlog(n)。
升序：借助大根堆
降序：借助小根堆
2）堆排序步骤
1.初始化数组为大根堆。
2.将array[0] 与 array[len - 1]交换
3.剩余n-1个元素重新调整为大根堆
4.重复执行交换、调整的步骤
image.png
image.png
