自学内容网 自学内容网

优先级队列(堆)

一、概念

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;
         }
     }
 }
  1. 如何创建小根堆:和大根堆逻辑相似,只是把交换的逻辑改成【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;
}
  1. 第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)!