AI 助理
备案控制台
开发者社区 云计算 文章 正文

一篇搞懂优先级队列(堆)（三）

2022-12-17 82
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 一篇搞懂优先级队列(堆)（三）

堆的其他应用-TopK 问题(经常出现)

拜托，面试别再问我TopK了！！！

关键记得，找前 K 个最大的，要建 K 个大小的小堆


基本方法

要求找前K个最小的元素 当然是要建大堆

要求找前K个最大的元素，当然是要建小堆

假设此时有10个元素，K=3

此时会引申出来两个问题：

1：为什么找前K个最小的元素 要建大堆？

为什么找前K个最大的元素，要建小堆？

2：堆的大小是多少：答：堆的大小为K的大小，也就是说K的值为多少，我们所建立的堆中的元素就有多少个


举例1(找前k个最小/最大的元素)

此时我们十个元素，如下所示：


此时我们要寻找这个堆里前3个最大的元素，那么此时堆的大小就为3，并且我们要建的是一个小根堆，下面来看步骤：

1:既然堆的大小为3，那么就让27，15，19这三个元素先组成小堆：组成的小堆如下所示:

2.png

2:下来到了18，然后让18与我们当前优先级队列的队头元素，也就是15去进行比较，发现18>15,那么就先让堆顶元素出堆，出堆的方法我们之前在出队列的时候已经讲过了，也就是交换我们的15与我们最后一个元素19，然后让15出堆即可：

2.png

发现此时仍是一个小堆后，将18入堆：

2.png

然后再调整为一个小根堆：

2.png

3：然后此时到了28，还是按照刚才18与15的比较方式去进行比较，现在需要比较的是28和18，还是刚才的方法往下比较即可，注意需要一直比较到37才能结束，此处我们就省略中间比较的过程，最后在我们堆中留下来的三个元素就是我们当前这个堆中前三个最大的元素：大家下来可以自己在草稿纸上自行演算，最后我们得出的结果为：

2.png

插入37后我们还会调整一次：最终结果如下所示：

2.png


下面大家想一想关于找堆中前K个最大/最小个元素的这个方法的时间复杂度是多少：


首先我们所建立的堆的大小是我们K值的大小，也就是说这个堆中的元素有K个，那么堆的高度为log2(K),又因为这个比较是在不断遍历元素与堆进行比较的，所以最终的时间复杂度为nlog2(k)(n为我们最原始堆中的元素个数)


代码实现

此处我们来实现找前K个最大的元素:来看我们的代码：


public class TestDemo {
    public static void topK(int[] array, int k) {
        //此时我们PriorityQueue底层默认是一个小根堆
        //此时创建一个大小为K的小根堆，因为是找前K个最大的元素
        Queue<Integer> qu = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //这样比较的话就是小根堆
                return o1 - o2;
            }
        });
        //2：遍历数组
        for (int i = 0; i < array.length; i++) {
            if (qu.size() < k) {
                qu.offer(array[i]);
            } else {
                if (qu.peek() < array[i]) {
                    qu.poll();
                    qu.offer(array[i]);
                }
            }
        }
        for (int i = 0; i < k; i++) {
            System.out.println(qu.poll());
        }
    }
    public static void main(String[] args) {
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        //此时我们传入的k值为3，也就是找前三个最大的元素
        //最后的结果得出前三个最大元素为37，49，65
        topK(array, 3);
    }
}

如果此时我们想找前K个最小的元素，方法该怎么写呢？来看代码：

public class TestDemo {
    public static void topK(int[] array, int k) {
        //此时我们PriorityQueue底层默认是一个小根堆
        //此时创建一个大小为K的大根堆
        Queue<Integer> qu = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //这样比较的话就是大根堆
                return o2 - o1;
            }
        });
        //2：遍历数组
        for (int i = 0; i < array.length; i++) {
            if (qu.size() < k) {
                qu.offer(array[i]);
            } else {
                //注意此处改成大于号
                if (qu.peek() > array[i]) {
                    qu.poll();
                    qu.offer(array[i]);
                }
            }
        }
        for (int i = 0; i < k; i++) {
        //每次出队列都会继续构建大根堆
            System.out.println(qu.poll());
        }
    }
    public static void main(String[] args) {
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        //最后的结果得出前三个最大元素为19,18,15
        topK(array, 3);
    }
}

因为是找前K个最小的元素，所以每次队头元素与数组遍历元素在进行比较的时候，当数组遍历的元素小于队头元素的时候，将队头元素删掉，并将我们数组遍历的元素入堆.并且在最开始建堆的时候一定建的是大堆，所以是return o2-o1。


举例2(找第K个最大/最小元素)

找第K个最大元素

下面仍是给定刚才的数组，找出这个数组第K个最大元素，其实仍然是紧接着刚才找前K个最大元素的代码，当找到前K个最大元素 后，此时我们的堆顶元素就是我们第K个最大的元素

2.png

例如刚才的数组，想要找到第三大的元素，我们拿肉眼可以看出来第三大的元素为37，那么要想找到第三大的元素，首先需要找到前三个最大的元素，我们在之前已经找到关于这个数组前三个最大的元素为37，49，65，堆图为：

2.png

可以看到37此时为堆顶元素，所以当数组遍历完成后，堆顶元素37就是第三大的元素


代码示例

public class TestDemo {
    public static void topK(int[] array, int k) {
        //此时我们PriorityQueue底层默认是一个小根堆
        //此时创建一个大小为K的小根堆
        Queue<Integer> qu = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //这样比较的话就是小根堆
                return o1 - o2;
            }
        });
        //2：遍历数组
        for (int i = 0; i < array.length; i++) {
            if (qu.size() < k) {
                qu.offer(array[i]);
            } else {
                //注意此处改成小于号
                if (qu.peek() < array[i]) {
                    qu.poll();
                    qu.offer(array[i]);
                }
            }
        }
        //打印我们第三个最大元素为37
        System.out.println(qu.peek());
    }
    public static void main(String[] args) {
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        //最后的结果为37
        topK(array, 3);
    }
}

找到第K个最小元素

下面仍是给定刚才的数组，找出这个数组第K个最小元素，其实仍然是紧接着刚才找前K个最小元素的代码，当找到前K个最小元素 后，此时我们的堆顶元素就是我们第K个最小元素

2.png

例如刚才的数组，想要找到第三小的元素，我们拿肉眼可以看出来第三小的元素为19，那么要想找到第三小的元素，首先需要找到前三个最小的元素，我们在之前已经找到关于这个数组前三个最小的元素为19，18，15,堆图为：

2.png

可以看到19此时为堆顶元素，所以当数组遍历完成后，堆顶元素19就是第三小的元素


代码示例

public class TestDemo {
    public static void topK(int[] array, int k) {
        //此时我们PriorityQueue底层默认是一个小根堆
        //此时创建一个大小为K的大根堆
        Queue<Integer> qu = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //这样比较的话就是大根堆
                return o2 - o1;
            }
        });
        //2：遍历数组
        for (int i = 0; i < array.length; i++) {
            if (qu.size() < k) {
                qu.offer(array[i]);
            } else {
                //注意此处改成大于号
                if (qu.peek() > array[i]) {
                    qu.poll();
                    qu.offer(array[i]);
                }
            }
        }
        //打印我们第三个最小元素为19
        System.out.println(qu.peek());
    }
    public static void main(String[] args) {
        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};
        //最后的结果为19
        topK(array, 3);
    }
}

堆的其他应用-堆排序(常考)

从小到大排序

还是对刚才的数组:假设我们要对这个数组从小到大排序，应该用大堆还是小堆？

答案当然是建一个大堆，下面来看步骤：

2.png

1:首先把这组数组建成一个大堆，如下所示：

2.png

2:然后把这个堆的堆顶元素与最后一个元素进行进行交换：

2.png

3：然后进行调整：49与28先进行调整：因为要维持成大根堆，首先49>34，要交换的是49，然后49>28，交换，交换后如下所示：

2.png

4:然后37>25，37>28，37与28交换，如下所示：

2.png

注意调整的时候是不能包含65的

5：此时49是我们当前第二大元素，让它与我们的15进行交换：交换后如下所示

2.png

6：然后再调整这棵树，此时我们会发现一个问题，每次我们要调整的那棵树都是0下标这棵树，37大于34，且37>15，于是两者进行交换，交换后如下所示：

2.png

7：28>15,于是两者进行交换,交换后如下所示

2.png

注意49不参与调整，所以除掉49，65以外，37是当前堆中的最大元素

8：此时继续把堆顶元素37与18再进行交换，后面的步骤都是跟之前一样的，依次往复，直到最后一个元素交换调整完毕，这里我就不再做过多的演示了.


代码示例

package heap;
public class HeapDemo {
    //堆的底层存储是顺序数组
    public int[] elem;
    //表示我们堆中的元素个数，同时也是我们堆调整时结束的标志
    public int usedSize;
    //初始化的时候为堆的底层数组创建一个默认的大小
    public HeapDemo() {
        this.elem = new int[10];
    }
    /**
     * 注意在这里为什么要传len
     * 传len的目的是告诉堆调整结束时的时间，因为每颗子树在进行向下调整时最后结束的条件是一样的
     * 就是当下标值大于堆中元素个数-1的时候就停止调整了
     * 所以len就代表每次调整结束的位置，而我们传入的len的值其实就是usedSize
     * adjustDown的时间复杂度为O(log2(n))
     *
     * @param parent
     * @param len
     */
    //向下调整
    public void adjustDown(int parent, int len) {
        //获取当前根节点的左子树的下标值
        int child = 2 * parent + 1;
        //child<len的时候说明有左子树，但是未必有右子树
        while (child < len) {
            //注意要加上child+1<len这个操作，原因是可能会没有右孩子只有左孩子
            if (child + 1 < len && this.elem[child] < this.elem[child + 1]) {
                child++;
            }
            //代码如果走到这里就代表child此时一定是左右孩子中的最大值所对应的下标
            if (this.elem[child] > this.elem[parent]) {
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                /*因为是从最后一棵树开始调整的  只要我们 找到了
                this.elem[child] <= this.elem[parent]，就说明后续就不需要循环了
                后面的都已经是大根堆了，所以直接break即可*/
                break;
            }
        }
    }
    //创建一个堆
    //createBigHeap方法的时间复杂度为O(nlogn)
    //其实本质上来说建立一个大根堆和建立一个小根堆方法的时间复杂度为O(n)
    public void createBigHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //此处的i其实就代表了我们的图中P每次的下标
        //this.usedSize - 1 - 1是为了获取我们堆中最后一棵子二叉树的父亲节点的下下标
        //第一次减1是因为我们按照层序遍历拍序号的时候我们是从0开始编号的，而第二次减1是已知子节点求父节点下标的公式
        //代表我们从最后一刻子树开始调整
        for (int i = (this.usedSize - 1 - 1) / 2; i >= 0; i--) {
            adjustDown(i, this.usedSize);
        }
    }
    //打印我们调整后的结果
    public void show() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
    /**
     * 堆排序方法
     */
    public void heapSort() {
        int end = this.usedSize - 1;
        for (int i = end; i >= 0; i--) {
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = tmp;
            adjustDown(0, end);
            end--;
        }
    }
}

注意：对于这个堆排序方法来说：


时间复杂度O(nlogn)

空间复杂度O(1)


测试类：

public class TestDemo {
    public static void main(String[] args) {
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        HeapDemo heapDemo = new HeapDemo();
        //[27, 15, 19, 18, 28, 34, 65, 49, 25, 37]
        System.out.println(Arrays.toString(array));
        //建立一个大根堆
        heapDemo.createBigHeap(array);
        //结果为65 49 34 25 37 27 19 18 15 28
        heapDemo.show();
        //从小到大对堆进行排序
        heapDemo.heapSort();
        //排序后的结果为15 18 19 25 27 28 34 37 49 65
        heapDemo.show();
    }
}

从大到小排序

从大到小的思路就是建立小堆，剩余比较的思路与刚才 一摸一样.


代码示例

package heap;
public class HeapDemo {
    //堆的底层存储是顺序数组
    public int[] elem;
    //表示我们堆中的元素个数，同时也是我们堆调整时结束的标志
    public int usedSize;
    //初始化的时候为堆的底层数组创建一个默认的大小
    public HeapDemo() {
        this.elem = new int[10];
    }
    /**
     * 注意在这里为什么要传len
     * 传len的目的是告诉堆调整结束时的时间，因为每颗子树在进行向下调整时最后结束的条件是一样的
     * 就是当下标值大于堆中元素个数-1的时候就停止调整了
     * 所以len就代表每次调整结束的位置，而我们传入的len的值其实就是usedSize
     * adjustDown的时间复杂度为O(log2(n))
     *
     * @param parent
     * @param len
     */
    //向下调整
    public void adjustDown(int parent, int len) {
        //获取当前根节点的左子树的下标值
        int child = 2 * parent + 1;
        //child<len的时候说明有左子树，但是未必有右子树
        while (child < len) {
            //注意要加上child+1<len这个操作，原因是可能会没有右孩子只有左孩子
            if (child + 1 < len && this.elem[child] > this.elem[child + 1]) {
                child++;
            }
            //代码如果走到这里就代表child此时一定是左右孩子中的最大值所对应的下标
            if (this.elem[child] < this.elem[parent]) {
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                /*因为是从最后一棵树开始调整的  只要我们 找到了
                this.elem[child] <= this.elem[parent]，就说明后续就不需要循环了
                后面的都已经是大根堆了，所以直接break即可*/
                break;
            }
        }
    }
    //创建一个堆
    //createBigHeap方法的时间复杂度为O(nlogn)
    //其实本质上来说建立一个大根堆和建立一个小根堆方法的时间复杂度为O(n)
    public void createSmallHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //此处的i其实就代表了我们的图中P每次的下标
        //this.usedSize - 1 - 1是为了获取我们堆中最后一棵子二叉树的父亲节点的下下标
        //第一次减1是因为我们按照层序遍历拍序号的时候我们是从0开始编号的，而第二次减1是已知子节点求父节点下标的公式
        //代表我们从最后一刻子树开始调整
        for (int i = (this.usedSize - 1 - 1) / 2; i >= 0; i--) {
            adjustDown(i, this.usedSize);
        }
    }
    //打印我们调整后的结果
    public void show() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
    /**
     * 堆排序方法
     */
    public void heapSort() {
        int end = this.usedSize - 1;
        for (int i = end; i >= 0; i--) {
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = tmp;
            adjustDown(0, end);
            end--;
        }
    }
}

测试类：


public class TestDemo {
    public static void main(String[] args) {
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        HeapDemo heapDemo = new HeapDemo();
        //[27, 15, 19, 18, 28, 34, 65, 49, 25, 37]
        System.out.println(Arrays.toString(array));
        //建立一个小根堆
        heapDemo.createSmallHeap(array);
        //结果为15 18 19 25 28 34 65 49 27 37
        heapDemo.show();
        //从大到小对堆进行排序
        heapDemo.heapSort();
        //排序后的结果为65 49 37 34 28 27 25 19 18 15
        heapDemo.show();
    }
}

面试题

1.查找和最小的K对数字

2.最后一块石头的重量

ab6brphvc5lw6
目录
相关文章
ice___Cpu
|
存储 算法 安全
数据结构 - 6（优先级队列（堆）13000字详解）
数据结构 - 6（优先级队列（堆）13000字详解）
ice___Cpu
46 0
小王90703
|
存储 安全 Java
数据结构优先级队列(堆)
数据结构优先级队列(堆)
小王90703
82 1
2的n次方_
|
3月前
|
存储 Java
【数据结构】优先级队列（堆）从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现，堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值，小根堆则相反。文章详细讲解了如何通过数组模拟实现堆，并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外，还介绍了堆排序及解决Top K问题的应用，并展示了Java中`PriorityQueue`的基本用法和注意事项。
2的n次方_
58 5
【数据结构】优先级队列（堆）从实现到应用详解
toKeep
|
7月前
|
存储 Java
优先级队列（堆）
优先级队列（堆）
toKeep
51 3
sky_qiyi
|
6月前
|
存储
数据结构学习记录——什么是堆（优先队列、堆的概念、最大堆最小堆、优先队列的完全二叉树表示、堆的特性、堆的抽象数据类型描述）
数据结构学习记录——什么是堆（优先队列、堆的概念、最大堆最小堆、优先队列的完全二叉树表示、堆的特性、堆的抽象数据类型描述）
sky_qiyi
133 2
不摸鱼的程序员
|
7月前
|
存储 算法 安全
堆 和 优先级队列（超详细讲解，就怕你学不会）
堆 和 优先级队列（超详细讲解，就怕你学不会）
不摸鱼的程序员
74 0
过。
|
7月前
|
存储 安全
堆与优先级队列
堆与优先级队列
过。
41 0
叶落闲庭
|
7月前
|
存储 算法
什么是堆，优先级队列的模拟实现
什么是堆，优先级队列的模拟实现
叶落闲庭
43 0
root8042965
|
7月前
|
存储
剑指Offer 面试题09. 用两个栈实现队列
剑指Offer 面试题09. 用两个栈实现队列
root8042965
47 0
敖云岚
|
存储 安全 Java
数据结构之第九章、优先级队列（堆）
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。关于PriorityQueue的使用要注意：2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常。
敖云岚
98 0