堆（堆排序，TOP K, 优先级队列）
1 概念解释
堆的定义：堆是一颗完全二叉树，分为大堆和小堆
大堆：一棵树中，任何父亲节点都大于等于孩子的节点，大堆的根结点最大
小堆：一棵树中，任何父亲节点都小于等于孩子节点，小堆的根节点最小
TOP K问题(元素个数远远大于K)
要求：从N个数中找出前K个最大的数(N >> K)
方法一： 假设是从100个数中找前10个最大的数，先用快速排序法对数据进行降序，前十个就是最大的，时间复杂度O(NlogN)
方法二： 将N个数依次push到大堆中，那么堆顶的元素肯定是最大的，然后pop K次，就找到了前K个最大的数，时间复杂度O(N+k*log2N后面会再次证明)。
那这是Topk问题吗？， 不完全是，
Topk问题的前提是： N非常大，若N为10亿、20亿，内存中无法存下这些数，只能存储在磁盘中，那上面的两种方式就不适用了
思路打开，可以先将前K个数建为小堆。
首先将前K个数建立成小堆， 然后将剩下N-K个数不断和堆顶比较，将大于堆顶的元素放入堆中，后然后向下调整后，最后堆中的K个数就是前K个最大的数。
时间复杂度为：K+（N-K）* logK 也就是O（NlogK）
注意：这里建立的是小堆而不是大堆。
因为如果是大堆，那么堆顶的数是堆中最大的，和剩下的N-K个数比较时，如果当前堆顶的数就是N个数中最大的，那么就把后面的数都挡在堆外了。这种只能找到N个数中最大的数。
总结：
TopK问题：通过建小堆，找到N个数中最大的前K个，建大堆，找到N个数中最小的前K个
堆排序：排升序建大堆，排降序建小堆
2 代码实现
建立堆的规则：
若下标从1开始时，其节点的计算为如下（树中第一个非叶子节点直接为len(最后一个节点的索引)/2）
若下标从0开始时，计算父节点，为**（当前索引 - 1） / 2**，左孩子：当前索引 × 2 +1；右孩子2: 当前索引 ×2 + 2
定义：
int parent(int root){
return root / 2;
}
int left(int root){
return root * 2;
}
int right(int root){
return root * 2 + 1;
}
上浮：
//上浮
public void swim(int low, int high){ //将[low...high]上浮为大顶堆，从high开始，由下往上
int i = high, j = i / 2;
while (j >= low){
if (a[i] > a[j]){
int temp = a[j];
a[j] = a[i];
a[i] = temp;
i = j;
j = i /2;
}else {
break;
}
}
}
下沉：
//下沉
public void sink(int low, int high){ //将[low...high]下沉为大顶堆，从low开始，由上往下
int i = low, j = 2 * low;
while (j <= high){
if (j + 1 <= high && a[j] < a[j+1]){
j++;
}
if (a[j] > a[i]){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i = j;
j = 2 * i;
}else {
break;
}
}
}
插入：
public void insert(int num){ //插入操作，插到堆的尾部，然后进行上浮
size++;
a[size] = num;
swim(1,size);
}
下沉:
public int delMax(){ //去除堆顶元素，删除堆的顶部元素，然后进行下沉
int temp = a[1];
a[1] = a[size];
size--;
sink(1,size);
return temp;
}
建堆（第一种是调用插入函数，从空开始建堆，是向上调整。第二种是提供现成的元素数组，从最后一个非叶子节点，向下调整）
static void TreeeAdjust(int a[], int low, int high){ //本质还是下沉操作，对low所指元素下沉
int i = low, j = 2 * low + 1; //i表示父节点，j表示左孩子，下标从0开始
while(j <= high){
if (j + 1 <= high && a[j] <= a[j+1]){ //j指向左右孩子较大的那个
j++;
}
//开始下沉
if(a[i] < a[j]){ //什么时候下沉，大顶堆-》当父节点小于子节点时；小顶堆-》当父节点大于子节点时下沉
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i = j;
j = 2 * i + 1;
}else {
break;
}
}
}
public static void bulidBigTree (int[] arr){ //构造大顶堆
int len = arr.length-1;
for (int i = len/2 - 1; i >= 0; i--){
TreeeAdjust(arr, i, len);
}
}
public static void sortBigTree(int[] arr){ //堆排序，交换元素以维持堆的定义。
int len = arr.length;
int i = len - 1;
while (i >= 0){
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
i--;
TreeeAdjust(arr, 0,i);
}
}
堆排序问题
升序：建大顶堆，然后交换堆顶和堆尾元素，重复调用下沉操作
降序：建大顶堆，然后交换堆顶和队尾元素，重复调用下沉操作（两次下沉结构一样，判断条件不同）
大堆：
static void TreeeAdjust(int a[], int low, int high){ //本质还是下沉操作
int i = low, j = 2 * low + 1; //i表示父节点，j表示左孩子，下标从0开始
while(j <= high){
if (j + 1 <= high && a[j] <= a[j+1]){
j++;
}
if(a[i] < a[j]){ //什么时候下沉，大顶堆-》当父节点小于子节点时；小顶堆-》当父节点大于子节点时下沉
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i = j;
j = 2 * i + 1;
}else {
break;
}
}
}
public static void bulidBigTree (int[] arr){ //构造大顶堆
int len = arr.length-1;
for (int i = len/2 - 1; i >= 0; i--){
TreeeAdjust(arr, i, len);
}
}
public static void sortBigTree(int[] arr){ //堆排序，交换元素以维持堆的定义。
int len = arr.length;
int i = len - 1;
while (i >= 0){
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
i--;
TreeeAdjust(arr, 0,i);
}
}
建立大堆和小堆关键的区别就在于下沉操作的判断条件
（将圈中的判断改成<就变成小堆）
大堆下沉： 当父节点小于子节点时（和较大的子节点交换位置）
小堆下沉：当父节点大于子节点时（和较小的子节点交换位置）
大堆上升：子节点大于父节点（直接判断）
小堆上升：当子节点小于父节点（直接判断）
每次分析时（按照这个最小的单位进行分析上浮和下沉）
3优先级队列
Java 优先队列 PriorityQueue
- Java 优先队列默认是小顶堆，小的先出队。
PriorityQueue<Integer> pq = new PriorityQueue<>()
建立大顶堆：
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->(b-a));
2.其他排序规则
//将pair按照key从大到小排序，key相同情况下，按照value从小到大排序。
PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(n, new Comparator<Pair<Integer, Integer>>() {
public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
if(o1.getKey() - o2.getKey() < 0) {
return 1;
} else if(o1.getKey() - o2.getKey() == 0){
if(o1.getValue() - o2.getValue() < 0) {
return -1;
} else {
return 1;
}
}
return -1;
}
});
// 在数组情况下，pair的key为数组值，value为下标，
// 实现上述排序的一种巧妙做法。注：nums[] 为数组
PriorityQueue<Integer> pqMin = new PriorityQueue<>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
if(nums[o1] - nums[o2] < 0) {
return -1;
} else if(nums[o1] - nums[o2] == 0){
if(o1 - o2 < 0) {
return -1;
}
}
return 1;
}
});
PriorityQueue<Integer> pqMax = new PriorityQueue<>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
if(nums[o1] - nums[o2] > 0) {
return -1;
} else if(nums[o1] - nums[o2] == 0){
if(o1 - o2 > 0) {
return -1;
}
}
return 1;
}
});
//Lambda表达式
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->(b-a));
优先队列常用方法
public boolean add(E e); //在队尾插入元素，插入失败时抛出异常，并调整堆结构
public boolean offer(E e); //在队尾插入元素，插入失败时抛出false，并调整堆结构
public E remove(); //获取队头元素并删除，并返回，失败时前者抛出异常，再调整堆结构
public E poll(); //获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构
public E element(); //返回队头元素（不删除），失败时前者抛出异常
public E peek()；//返回队头元素（不删除），失败时前者抛出null
public boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素（从队头到队尾遍历）
public Iterator<E> iterator(); //迭代器
插入元素 offer（）方法，返回值boolean，再次调整堆结构
删除元素 poll（）方法，返回堆顶元素，再次调整堆结构
获取堆头元素 peek（）方法，返回堆顶元素
判断队列是否为空** isEmpty(); **
获取队列中元素个数**size(); **
判断队列中是否包含指定元素（从队头到队尾遍历）**contains(Object o); **
参考链接：
https://blog.csdn.net/weixin_46016019/article/details/123774875