堆（堆排序，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()；//返回队头元素（不删除），失败时前者抛出nullpublic boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素（从队头到队尾遍历）
public Iterator<E> iterator(); //迭代器