（1）逻辑概念上：完全二叉树（满二叉树或者是从左往右依次变满的二叉树）
（2）存储表示：数组从0出发的连续一段表示一颗完全二叉树，使用size描述该树有多少结点，在i位置上的结点，其左孩子下标为（2*i+1），右孩子下标为（2*i+2），父节点为（i-1）/2.
（3）分类：
大根堆：堆顶为整个堆最大的元素，同样的每个子树也满足子树的最大值是头结点的值
小根堆：堆顶为整个堆最小的元素，同样的每个子树也满足子树的最小值是头结点的值
两个重要过程： heapinsert：向上跟父节点比较调整的过程
public static void heapinsert(int[] arr, int index){
while(arr[index] > arr[(index - 1)/2]){//包含index在0位置的情况
swap(arr, index, (index-1)/2);
index = (index - 1) / 2;
}
}
heapify：向下跟子节点比较调整的过程
public static void heapify(int[] arr, int index, int heapSize){
int left = index * 2 + 1; //左孩子的下标
while(left < heapSize){ //如果有孩子
//如果有右孩子，找出左右孩子中的较大的下标
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
//将较大孩子和自己比较，取较大的
largest = arr[index] >= arr[largest] ? index : largest;
if(index == largest) break;//如果自己比孩子都大，则停止下沉
swap(arr, index, largest);//否则交换，继续比较
index = largest;
left = index * 2 + 1;
}
}
堆排序（由小到大——大根堆）时复：O(N*logN)，空复：O(1)
先形成堆，再从堆顶弹出元素，从后往前放入数组。
形成堆时：
法1：从数组的前面开始，依次向堆中添加元素建堆
法2：假设所有元素已经构成了堆形的树，然后从后往前下沉，先调整好局部小堆，在调整大堆。最后一层约有N/2个节点，每个结点处理1次（看一眼）；倒数第二层约有N/4个节点，每个结点处理2次（看1眼，可能向下移动1步）....所有的相加为总的操作次数（式1）。将该式左右都乘以2（式2），将两式子错位相减，可以得到最后的时间复杂度为O(N)。
//由小到大排序
public static void heapSortMax(int[] arr){
if(arr == null || arr.length < 2) return;
int heapSize = 0;
//让数组构成大根堆，法1：O(N*logN)
// for(int i = 0; i < arr.length; i++){//构成一个大根堆 O(N)
// heapinsert(arr, i); //O(logN)
// }
//让数组构成大根堆，法2：O(N)
for(int i = arr.length - 1; i >= 0; i--){
heapify(arr, i, arr.length);//这里的第三个参数是堆的大小，由于是倒序依次下沉的，所以取最大值
}
//大根堆堆顶元素依次弹出
heapSize = arr.length;
swap(arr, 0, --heapSize);//如果将先swap后heapify都写到循环中，就多执行了一次没有意义的heapify
while (heapSize > 0 ){//O(N)
heapify(arr, 0, heapSize);//需要 len-1 次heapify即可。O(logN)
swap(arr, 0, --heapSize);//O(1)
}
}
由大到小（小根堆），Java中系统自带的优先级队列默认是小根堆
//小根堆
public static void heapnsert_min(int[] arr, int index){
while (arr[index] < arr[(index - 1) / 2]){
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void heapify_min(int[] arr, int index, int heapSize){
int left = index * 2 + 1;
while (left < heapSize){
//注意这里只能是满足条件才能取右孩子，否则如果是else取右孩子，还存在右孩子不存在的情况，就会越界
int less = (left+1 < heapSize) && arr[left + 1] < arr[left] ? left + 1 : left;
less = arr[less] < arr[index] ? less : index;
if(less == index) break;
swap(arr, less, index);
index = less;
left = index * 2 + 1;
}
}
//从大到小排序
public static void heapSortMin(int[] arr){
//建小根堆
for(int i = arr.length - 1; i >= 0; i--){
heapify_min(arr, i, arr.length);
}
//从堆顶依次弹出
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while (heapSize > 0){
heapify_min(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
例题：
解决：使用默认的优先级队列 PriorityQueue将前（k+1）个元素建立一个小根堆，堆顶的元素一定放在arr[0]的位置，依次在向后添加新的元素构建新的小根堆，将弹出元素放入arr[1]的位置，直到整个数组的后（k+1）个元素都在堆中，然后从小到大依次弹出放入数组中。时间复杂度为O(N*logK)
如果考虑到堆的扩容问题，是成倍扩容，即扩容logN次，每次扩容完都要将原来的元素拷贝，即单次扩容代价是O（N），所以总的操作次数是O(N*logN)，每个元素均摊的扩容代价为O[(N*logN)/N] = O(logN)
public static void sortedArrDistanceLessK(int[] arr, int k){
PriorityQueue heap = new PriorityQueue<>();
int index = 0;
for(; index < Math.min(k, arr.length); index++){//把前（k+1）个放入小根堆
heap.add(arr[index]);
}
int i = 0;
for(; index < arr.length; index++, i++){//弹出一个，添加一个，直到添加完
arr[i] = heap.poll();//堆顶弹出放入k范围下的第一个位置
heap.add(arr[index]);//k范围整体后移
}
while (!heap.isEmpty()){//堆中剩余元素按顺序弹出
arr[i++] = heap.poll();
}
}
注意：
系统给的优先级队列（堆结构）与自己手写堆的区别：系统堆结构在初始建堆时结构元素大小已经固定，当如果想改变某一个数重新调整成堆时，可能需要重新扫描所有元素，heapify和heapinsert，有很高的代价，这时就需要手写堆，直接判断该变化的数是需要heapify还是heapinsert。如果只是简单的需要添加和弹出数，可以使用系统堆，涉及到更改堆元素，需要手写
比较器：（1）实质：重载比较运算符
（2）可以很好的应用在比较特殊的排序规则上
（3）可以很好的应用在根据特殊标准排序的结构上
实现方法：自己编写一个比较器类实现Comparator<要比较的类>接口，重新compare
！！！规则：
在Arrays.sort()、 PriorityQueue、TreeSet中都可以传入比较器对象，按照给定的要求建立。在堆中，比较器中排在前面的数应该放在上面，这样默认的小根堆也可以改成大根堆
