优先级队列(堆)

一、概念

1.1 什么是优先级队列及如何实现

1. 什么是优先级队列：队列是一种先进先出(FIFO)的数据结构，但如果操作的数据带有优先级并且我们需要处理优先级更高的队列，此时光用【队列】不太合适，故而我们引入了【优先级队列(PriorityQueue)】
2. 如何实现优先级队列：JDK1.8中的PriorityQueue底层使用了堆这种数据结构来模拟优先级队列

1.2 什么是堆

1. 概念：堆实际就是在完全二叉树的基础上进行了一些调整 + 以顺序存储(数组)的方式存储二叉树
   • 对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低

1.3 如何根据当前结点找到其他结点

1. 已知i下标，求父亲结点下标：(i - 1) / 2
2. 已知父亲结点为i，求孩子结点下标：左孩子结点为【2i + 1】，右孩子结点为【2i + 2】

二、堆的使用

2.1 结构

public class TestHeap {

    public int[] elem;
    public int usedSize;   //堆里的有效元素个数

    public TestHeap() {
        this.elem = new int[10];  //设置该堆里最多只有10个元素
    }
}

2.2 创建堆(以大根堆举例)

1. 思路：从最后一个子树开始，找到左右结点的最大值，如果最大值(child)比该子树的根结点值大，就执行交换操作并检查交换后包含的子树是否都是大根堆(让parent等于child，child继续往下走，除非child < useSize，表示这棵树已经整完了)
   • 为什么要从下往上走：在下面已经是大根堆的情况下，比较方便调整
   • 如何确定最后一棵子树的位置：最后一个结点下标是elem数组的长度 - 1，此时根据【求父亲结点的公式】，可得最后一个子树的根节点为【((elem.length - 1) - 1) / 2】
   • 调整完一棵子树后如何调整到下一棵：调整完的子树根结点 - 1
   • 如何确定当前这棵树已经调整完了：该点的左节点下标 < useSize（因为至少会有一个左孩子）
2. if(child + 1 < len && elem[child] < elem[child+1])：为什么需要前一个条件，因为如果一个结点只有左孩子，没有右孩子，此时child + 1是会越界的。child + 1 < len保证了数组不会越界
3. 创建堆的时间复杂度：O(n)
   

 public void createHeap(int[] array) {
     for (int i = 0; i < array.length; i++) {
         elem[i] = array[i];
         usedSize++;
     }
     
     //把原始数据 给到了 elem数组
     for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
     //为什么不用(elem.length - 1 - 1) / 2，因为数组的长度为10并不意味着这里有10个元素
         shiftDown(parent,usedSize);
     }
 }

//向下调整，时间复杂度为O(logN)，因为最坏的情况是从root调整
 private void shiftDown(int parent,int len) {
     int child = 2 * parent+1;

     while (child < len) {
         if(child + 1 < len && elem[child] < elem[child+1]) {
             child = child + 1;
         }
         if(elem[child] > elem[parent]) {
             int tmp = elem[child];
             elem[child] = elem[parent];
             elem[parent] = tmp;
             parent = child;
             child = 2 * parent+1;
         }else {
             //此时本身 就是一个大根堆
             break;
         }
     }
 }

3. 如何创建小根堆：和大根堆逻辑相似，只是把交换的逻辑改成【elem[child] > elem[child+1]】而已

2.3 把一个新元素插入到堆中

1. 思路：插入一个数据后，依旧需要保证当前堆事大根堆/小根堆 ---- 向上调整
   • 把新的数据插入到数组的最后一个位置，然后不断比较孩子结点和父亲节点，如果孩子>父亲，就交互喊，如果【小于】或者【child为0已经把全部的树整理完了】就结束操作
2. 创建堆的第二种方式：当数组内一个数据都没有的时候，我们也可以一个个去插入数据，不断向上调整直到创建出堆。但这种方式比第一种时间复杂度更高

public void push(int val) {
    //1. 检查满，如果满了就扩容
    if(isFull()) {
        elem = Arrays.copyOf(elem,2*elem.length);
    }
    //2、存数据
    elem[usedSize] = val;
    usedSize++;
    shiftUp(usedSize-1);
}

public boolean isFull() {
    return usedSize == elem.length;
}

public void shiftUp(int child) {
    int parent = (child-1)/2;
    while (child > 0) {
        if(elem[child] > elem[parent]) {
            int tmp = elem[child];
            elem[child] = elem[parent];
            elem[parent] = tmp;
            child = parent;
            parent = (child-1)/2;
        }else {
            break;
        }
    }
}

2.4 删除堆内的一个元素

1. 思路：只能删除堆顶元素
   • 将堆顶元素对堆中最后一个元素交换
   • 将堆中有效数据个数减少一个
   • 对堆顶元素进行向下调整(只需要调整这一棵树即可)

public void poll() {
    if(empty()) {
        throw new HeapEmptyException("优先级队列是空的！");
    }
    
    int tmp = elem[0];
    elem[0] = elem[usedSize-1];
    elem[usedSize-1] = tmp;
    usedSize--;
    
    shiftDown(0,usedSize); //向下调整0下标这棵树
}

public boolean empty() {
    return usedSize == 0;
}

2.5 模拟peek()方法

public int peek() {
    if(empty()) {
        throw new HeapEmptyException("优先级队列是空的！");
    }
    return elem[0];
}

三、PriorityQueue 介绍

3.1 什么是PriorityQueue

1. 概念：Java当中的一个集合类，是优先级队列，实现了Queue这个接口。底层使用了堆数据结构，且默认情况下是小根堆
   • PriorityBlockingQueue：Java还提供了PriorityBlockingQueue，也是优先级队列
   • 两者区别：PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的

3.2 如何使用PriorityQueue

元素要求

1. 要求能比较：因为涉及到带有优先级的堆，根据堆的原理，每插入一个元素都会涉及到【比较】，所以如果【没有写比较方式/压根不能比较】，会出ClassCastException异常(只有一个元素时还没涉及到比较，不会出错)
   • 初始化如果传入的是对象，那么要求这个类是实现Comparable接口的
2. 不为null：不能插入null对象，否则会抛出NullPointerException
3. 没有容量限制：内部可以自动扩容

结构介绍

构造方法

添加元素offer()

1. 源码分析：
   

如何创建一个大根堆

1. 方式一：实现Comarable接口 + 重写comparTo方法
   
2. 方式二：把比较器在构造方法阶段传过去

删除元素poll()

1. 源码分析：
   

扩容grow()

1. 源码分析：在集合中，所有的扩容都要去看grow()方法
   

四、TopK问题

1. 场景描述：当要求诸如【找到前k个最小的数】的这种题

   • 方法一是“排序之后，取5个数字”

   • 方法二是“建立小根堆，然后弹出5次数据”。但是方法二的时间复杂度很高(建堆为O(N)，每次调整是log(N)，总体为O(N) + k * log(N))

   • 最好的方法是【利用TopK的解决方法】

2. 前K个最小的元素：
   • 操作：
     • 先建立大小为K的大根堆（因为要求这个堆里面元素都是最小的，那么堆顶元素一定是k个数中最大的）
     • 从第K+1个元素开始，每个元素都和栈顶元素进行比较，如果比堆顶元素小就入堆
   • 时间复杂度分析：极端情况下，从第K+1个元素开始，每个元素都要调整，最终为N * log(K)

public static int[] smallestK(int[] arr, int k){
    Queue<Integer> maxHeap = new PriorityQueue<>(new ComparByBig());

    for (int i = 0; i < k; i++){
        maxHeap.offer(arr[i]);
    }

    for (int i = k; i < arr.length; i++){
        int top = maxHeap.peek();

        if (top > arr[i]){
            maxHeap.poll();
            maxHeap.offer(arr[i]);
        }
    }

    int[] ret = new int[k];
    for (int i = 0; i < k; i++){
        ret[i] = maxHeap.poll();
    }

    return ret;
}

3. 第K小的元素：排序整个数组，然后取元素
   • 操作：将0下标元素和最后一个元素交换，此时最后一个元素一定是最大的，且该元素已经来到了合适的位置上，然后我们只需要调整0下标这棵树即可。下次交换时，最后一个元素也就不用进入调整的范围了

public void heapSort(){
int end = useSize - 1;
while (end > 0){
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0, end);
end--;
}
}

private void shiftDown(int parent,int len) {
    int child = 2 * parent+1;

    while (child < len) {
        if(child + 1 < len && elem[child] < elem[child+1]) {
            child = child + 1;
        }
        if(elem[child] > elem[parent]) {
            int tmp = elem[child];
            elem[child] = elem[parent];
            elem[parent] = tmp;
            parent = child;
            child = 2 * parent+1;
        }else {
            //此时本身 就是一个大根堆
            break;
        }
    }
}

原文地址：https://blog.csdn.net/wuweixiaoyue/article/details/142486785

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！