数据结构之优先级队列(堆)及top-k问题讲解

2023-12-13 05:56:52

?💕"哪里会有人喜欢孤独,不过是不喜欢失望。"💕

作者:Mylvzi?

?文章主要内容:数据结构之优先级队列(堆)?

?

一.优先级队列

1.概念

? 我们已经学习过队列,队列是一种先进先出(FIFO)的数据结构,但是在有些情况下,数据的进出是有优先级的,优先级高的往往需要先"出",优先级低的就需要后"出",此时普通的队列就无法完成这样的操作(也就是数据在插入到队列中后,还需要根据优先级进行位置调整),需要另外一种数据结构--优先级队列?PriorityQueue来实现

? 在实际生活中PriorityQueue的场景经常存在,比如你在打游戏的时候,如果有来电,系统应该优先处理来电。

? 在这种场景下,数据结构需要实现两个最基本的操作"返回优先级最高的对象"和"添加新的数据"

二.优先级队列的模拟实现

? jdk1.8中的PriorityQueue 底层就使用了"堆"这种数据结构,堆实际上就是经过优先级调整的完全二叉树

注:这里的优先级在堆中的体现一般是所存储数据的大小?

1.什么是堆?

? 堆是一种把元素按大小排列的完全二叉树,堆就是进行数据高效组织的另一种形式

从小到大排列:小根堆(每棵树的根节点的值比当前树的所有孩子都小)

从大到小排列:大根堆(每棵树的根节点的值比当前树的所有孩子都大)

大根堆示例:

小根堆示例:
?

2.堆的存储方式

? 堆其实是一颗完全二叉树,那么在存储的时候就可以使用顺序表进行数据的存储;而对于非完全二叉树来说,则不适合使用顺序表存储数据,因为会导致空间资源的浪费

? 既然是一颗完全二叉树,那就具有完全二叉树的一些性质

  • 如果i为0,则i对应的结点是根节点;i的父节点的下标为(i-1)/2
  • 由父节点的下标i可得左孩子的下标:2*i+1,右孩子的下标:2*i+2

3.堆的创建

一般都是根据数组去创建堆? 使数组中的元素在二叉树中排列时呈现某种顺序

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据,如果将其创建成堆呢?

观察集合,此时是无序的,我们需要通过调整将其设置为大根堆/小根堆

1.堆的实现

1.大根堆的实现

图解:

可见实现大根堆的核心思路在于"向下调整",对已有的数据进行向下调整,使其符合规定的顺序

向下调整的步骤:

  1. ?先获取到最后一棵子树的根节点的下标 parent = (usedSize - 1- 1)/2
  2. 获取到左右孩子结点的最大值(先获取左孩子,再判断左右孩子谁的值更大)
  3. 如果孩子节点的值>根节点的值,交换,交换之后需要堆parent重新赋值为child,继续向下调整
  4. 如果孩子节点的值<根节点的值,不交换,parent--;

对于2:为什么先获取左孩子的结点呢?因为对于一个完全二叉树来说,其最后一棵子树一定有左孩子,但是不一定有右孩子。

代码实现?

    // 根据传入的数组  将他们调整为大根堆

    public int[] elem;
    public int usedSize;

    public TestHeap(int size) {
        this.elem = new int[size];
    }

    // 初始化堆
    public void initHeap(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            this.elem[i] = arr[i];
            this.usedSize++;
        }


    }

    // 实现大根堆

    /**
     * 从最后一棵子树的根节点开始,进行向下调整,一直调整到root
     */
        // 向下调整
    public void createHeap() {
        // 从最后一棵子树的根节点开始
        for (int parents = (usedSize-1-1)/2; parents >= 0; parents--) {
            shiftDown(parents,usedSize);
        }
        
    }

    private void shiftDown(int parents, int usedSize) {
        // 先获取左孩子的下标
        int child = 2*parents + 1;
        
        // 进行向下调整
        while (child < usedSize) {
            // 先判断左右孩子的值是谁更大
            if(child+1 < usedSize && elem[child] < elem[child+1]) {
                // 存在右孩子  且右孩子的值比左孩子的大
                child++;
            }
            
            if(elem[child] > elem[parents]) {
                // 如果孩子结点的值比根节点大  交换
                swap(child,parents);
                parents = child;
                child = 2*parents + 1;
            }else {
                // 如果根节点就是最大值  直接翻一下
                break;
            }
        }
    }

    // 交换函数
    private void swap(int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
2.小根堆的实现

实现小根堆的逻辑是相同的,只需要在进行向下调整的时候改一下交换的逻辑

    // 实现小根堆
    public void createHeap2() {
        // 从最后一棵子树的根节点开始
        for (int parents = (usedSize-1-1)/2; parents >= 0; parents--) {
            shiftDown(parents,usedSize);
        }

    }

    private void shiftDown2(int parents, int usedSize) {
        // 先获取左孩子的下标
        int child = 2*parents + 1;

        // 进行向下调整
        while (child < usedSize) {
            // 先判断左右孩子的值是谁更大
            if(child+1 < usedSize && elem[child] > elem[child+1]) {
                // 存在右孩子  且右孩子的值比左孩子的小
                child++;
            }

            if(elem[child] < elem[parents]) {
                // 如果孩子结点的值比根节点小  交换
                swap(child,parents);

                // parent中大的元素向下移动  可能会造成子树不满足堆的性质  继续进行向下调整
                parents = child;
                child = 2*parents + 1;
            }else {
                // 如果根节点就是最大值  
                break;
            }
        }
    }

向下调整的时间复杂度:
? ?最坏的情况就是从根节点一直比到叶子节点,比较的次数就是完全二叉树的高度,O(logn)

其他情况比较的次数都是常数次,对于时间复杂度来说,一般只考虑最坏情况

2.堆的创建

? 在向下调整的代码中我们已经实现了堆的创建

    // 堆的创建
    public void createHeap() {
        // 从最后一棵子树的根节点开始
        for (int parents = (usedSize-1-1)/2; parents >= 0; parents--) {
            shiftDown(parents,usedSize);
        }
    }

向下调整的时间复杂度是?O(logn),那"建堆"的时间复杂度是多少呢?请看下面的推导

?

注:
1.堆建立的时间复杂度需要考虑两方面,每层的结点数,以及每个结点向下调整的最坏情况

2.堆的时间复杂度的推导需要使用到数列中常见的一种方法"错位相减"

3.堆的时间复杂度一定要回手写推导,面试中有可能会考到!!!

3.在堆中添加元素

? 要求:添加之后仍满足大根堆的形式

说明:

  1. 在堆中插入一个新的元素之后,需要仍保持堆的性质,此时需要进行向上调整,直到调整到合适的位置;
  2. 由于堆的存储结构是一个顺序表,所以当顺序表满时,需要进行扩容?;同时,堆的插入对应的就是顺序表的尾插

代码实现:

// 在堆内添加元素
    /**
     * 插入到最后一个位置(保证是一个完全二叉树,且方便后续操作)
     * 向上调整
     */

    public void offer(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }

        this.elem[usedSize] = val;
        shiftUp(usedSize);
        this.usedSize++;
    }

    private void shiftUp(int child) {
        int parent = (child-1)/2;
        
        // == 0此时就是根节点了  不需要再去向上调整
        // 需要一直调整到根节点
        while(child != 0) {
            if(elem[child] > elem[parent]) {
                swap(child,parent);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

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

4.删除优先级最高的元素(数组的首元素)

? 堆的删除对应队列的"出队"操作,只不过堆的删除出的是优先级最高的元素

? 对于堆来说,优先级最高的元素位于堆顶,也就是顺序表的首元素,那如何进行堆的删除操作呢?

? 最直观的想法就是先保存堆顶元素,然后挪动堆顶元素之后的所有元素,使其都向前挪动一个位置,再对挪动之后的结果重新进行向下调整。这种方法实际上是可行的,但是时间复杂度过高,效率较低,这种方法的时间复杂度是挪动数据的时间复杂度O(n)与向下调整的时间复杂度O(logN)之和

? 当然还有另一种效率更高的实现方法,先交换堆顶和堆尾的元素,再进行向下调整,此方法的时间复杂度是交换的时间复杂度O(1)与向下调整的时间复杂度O(logN),效率明显比大量挪动数据更高

代码实现:

// 删除  一定是删除优先级最高的元素  最后返回优先级最高的那个元素
    public int poll() {
        // 优先级最高的元素就是顺序表elem 的首元素
        int tmp = elem[0];
        swap(0,usedSize-1);
        this.usedSize--;
        
        // 只需对堆顶元素进行向下调整
        shiftDown(0,usedSize);
        
        return tmp;
    }

注:

? 交换堆顶和堆尾元素这一操作还有另一考量,因为堆尾元素一定是优先级最低的元素,出队一定是最后一个进行出队,交换之后,堆顶是优先级最低的元素,就保证了其余元素都是优先级比堆顶元素更高,此时只需对堆顶元素进行向下调整即可,而不是从最后一棵子树的根节点开始进行调整

总结:删除堆中元素的三步骤

  1. 交换堆顶和堆中最后一个元素
  2. 删除最后一个元素
  3. 将堆顶元素进行向下调整

三.常用接口介绍

1.PriorityQueue的特性

? Java的集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,此处主要介绍PriorityQueue

使用PriorityQueue的注意事项

  1. 需要导包,即:import java.util.PriorityQueue;
  2. PriorityQueue中存放的数据必须能够进行大小的比较,不能够插入无法比较的对象,否则会报错
            PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();
            priorityQueue1.offer(1);
            priorityQueue1.offer(2);
    
            PriorityQueue<Student> priorityQueue2 = new PriorityQueue<>();
            priorityQueue2.offer(new Student());
            priorityQueue2.offer(new Student());// 报错  

3.不能插入null,否则会报空指针异常

4.插入(向上调整)和删除的操作的时间复杂度都是O(logN)

5.?PriorityQueue默认是小根堆,也就是根节点的值比子节点的值小

?

        PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();
        priorityQueue1.offer(1);
        priorityQueue1.offer(2);
        priorityQueue1.offer(3);
        priorityQueue1.offer(4);
        priorityQueue1.offer(5);

        System.out.println(priorityQueue1.poll());// 输出1

2.?PriorityQueue常用接口介绍

1.构造方法

1.1不含参的构造方法
    // 不含参的构造方法
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
    // 默认容量是11
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
1.2?指定容量的构造方法
    // 指定容量的构造方法
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }
1.3指定容量 ?并接受比较器的构造方法(最核心的一个构造方法)
    // 指定容量  并接受比较器的构造方法
    public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        
        // 如果初始容量<1  就抛出异常  但实际上源码中也说了  <1这个条件并不是必需的  只不过是为了和1.5保持一致设置的条件
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }
?1.4利用其他集合创建一个优先级队列

只要实现了Collection的集合都能作为参数参与创建一个优先级队列

PriorityQueue(Collection<? extends E>?c)??用一个集合来创建优先级队列

        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(12);
        list.add(13);

        PriorityQueue<Integer> priorityQueue =
                new PriorityQueue<>(list);
        System.out.println(priorityQueue.toString());// 输出1 12 13

2.PriorityQueue的扩容机制

PriorityQueue的存储结构是顺序表,在不断添加数据的时候涉及到扩容问题,下面来研究一下PriorityQueue中是如何进行扩容的

先来看offer对应的源码

    public boolean offer(E e) {
        
        // 为空 直接抛出异常  不能插入空指针
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        
        // 进行扩容
        if (i >= queue.length)
            // grow方法内部是扩容的机制
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else  // 向上调整
            siftUp(i, e);
        return true;
    }

接下来看grow方法的实现?



3.如何实现大根堆

PriorityQueue默认是小根堆,想要实现大根堆则需要重新构建比较逻辑,使用Comparator接口,下面以整数的比较为例实现大根堆

1.方法一:直接构造一个比较器
        // 构造比较器 实现大根堆
        class IntCmp implements Comparator<Integer> {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        }

        PriorityQueue<Integer> priorityQueue =
                new PriorityQueue<>(new IntCmp());
        priorityQueue.offer(1);
        priorityQueue.offer(2);
        priorityQueue.offer(33);
        priorityQueue.offer(44);
        priorityQueue.offer(55);

        System.out.println(priorityQueue.poll());// 输出55
2.方法二:使用匿名内部类
        // 使用匿名内部类
        PriorityQueue<Integer> priorityQueue =
                new PriorityQueue<>(new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o2.compareTo(o1);
                    }
                });

        priorityQueue.offer(1);
        priorityQueue.offer(2);
        priorityQueue.offer(33);
        priorityQueue.offer(44);
        priorityQueue.offer(55);

        System.out.println(priorityQueue.poll());// 输出55
3.方法三:使用lambda表达式(推荐)?
        // 使用lambda表达式
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(
                (o1,o2) ->{return o2.compareTo(o1);}
        );

        priorityQueue.offer(1);
        priorityQueue.offer(2);
        priorityQueue.offer(33);
        priorityQueue.offer(44);
        priorityQueue.offer(55);

        System.out.println(priorityQueue.poll());// 输出55

四.重点:top-k问题的三种解决方法

https://leetcode.cn/problems/smallest-k-lcci/description/

1.最简单的思路:对数组进行排序

// 解法1
    public int[] smallestK1(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0) return ret;

        Arrays.sort(arr);

        // 排序之后  arr从小到大排列完毕
        for (int i = 0; i < k; i++) {
            ret[i] = arr[i];
        }

        return ret;
    }

?

2.直接使用堆(优先级队列)的特性? 创建小根堆? poll k次即可

// 解法2
    public int[] smallestK2(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0) return ret;

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

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

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


        return ret;
    }

3.建立一个k个结点的大根堆? 再与数组剩余元素进行比较(重点掌握)

步骤:

  1. 先将前k个元素创建为大根堆(k 是因为我最后要返回k个元素)
  2. 将数组中剩余的元素依次去和堆顶元素进行比较,如果小于堆顶元素,插入堆中
  3. 返回容量为k的大根堆

// 解法3  效率最高的一种方法  创建一个具有k个结点的大根堆
    
    // 注意  优先级队列默认是小根堆  要实现大根堆  需要先创建一个实现了Comparator接口的对象
    class IntCmp implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0) return ret;

        // 创建一个具有k个结点的大根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());

        for (int i = 0; i < k; i++) {
            // 将前k个元素做成大根堆
            priorityQueue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            // 去和栈顶元素比较
            if (arr[i] < priorityQueue.peek()) {
                // 证明栈顶元素不是前k个最小的元素  要删除
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

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

        return ret;
    }

?时间复杂度分析:

前两种方法对于数据量特别大的情况十分不友好!占用的内存太大?

变式:

求数组中第k大/小元素
// 求数组中第k大/小元素

    //  前k个元素存储到小根堆中  堆里存放最大的k个元素 以小根堆的形式存储  则堆头一定是第k大的元素
    public int maxKestK(int[] arr, int k) {
        if(arr == null || k <= 0) {
            throw new ArrayEmptyException("不含有元素或k不合法");
        }

        // 创建一个具有k个结点的大根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        for (int i = 0; i < k; i++) {
            // 将前k个元素做成小根堆
            priorityQueue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            if (arr[i] > priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        return priorityQueue.poll();

    }

五.堆排

? 堆排序即利用堆的思想进行排序,堆排序的过程可以分为两步

  1. 确定排序方式:升序--建立大根堆? 降序--建立小根堆
  2. 利用堆删除的思想(向下调整进行堆排)

图解:

代码实现

    // 堆排序
    // 升序  从小到大  创建大根堆
    // 降序  从大到小  创建小根堆

    /**
     * 升序  调整为大根堆  堆首元素一定是最大的
     * 交换堆首和堆尾元素  向下调整(不包含被调下去的最大元素)  使第二大的元素位于堆顶
     * 重复上述操作  每次都是堆首元素和堆尾元素进行交换
     */

    public void headSort() {
        int end = usedSize-1;
        while(end > 0) {
            swap(0,end);
            shiftDown(0,end);
            end--;
        }
    }

    private void shiftDown(int parent, int usedSize) {
        int child = 2 * parent+1;// 得到左孩子的下标
        while (child < usedSize) {
            // 首先要保证child是左右孩子最大元素的下标
            if(child + 1 < usedSize && elem[child] < elem[child+1]) {
                // 有右孩子  且右孩子的值比左孩子大
                child++;
            }

            // 此时child就是值最大孩子的下标
            if(elem[child] > elem[parent]) {
                swap(child,parent);
                parent = child;
                child = 2 * parent+1;
            }else {
                break;
            }
        }
    }

总结:

堆排时要选择好排序的顺序,如果是升序排序就创建大根堆,如果是降序排序就是用小根堆

以升序排序为例,创建一个大根堆存储数据,再不断交换堆顶和堆尾元素(此时一定是最大元素放到堆尾,最小元素放到堆顶),再进行向下调整,向下调整的数据范围并不报错刚刚被挪动到堆尾的元素,使整个堆仍然保持大根堆的性质,这样最大的元素就被移动到最后,依次操作,每次都可以把当前数据范围内的最大元素移动到最后,最后创建出的堆中存储的数据就是升序排序的

这种"逆向思维"在堆中很常见,想让堆顶是最小的元素,就先创建大根堆,再不断地挪动数据,向下调整

文章来源:https://blog.csdn.net/Mylvzi/article/details/134167220
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。