龙空技术网

Leetcode:找出最小的K个数(最小堆,大厂必考)

元面试 176

前言:

此时同学们对“关于堆的判断”大致比较着重,大家都想要了解一些“关于堆的判断”的相关内容。那么小编在网摘上收集了一些关于“关于堆的判断””的相关内容,希望我们能喜欢,咱们一起来学习一下吧!

题目描述

《Leetcode,面试题17.14,最小k个数》

设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。

0 <= len(arr) <= 1000000 <= k <= min(100000, len(arr))题目分类

树 > 堆

为什么容易被选为面试题?

1、最小堆、最大堆在Java的很多数据结构中都有应用。

例子1:我前面的线程池讲解中《京东字节大厂热门面试题:讲讲线程池的工作原理?》,优先级任务对类PriorityBlockingQueue,使用的就是数组形式的小顶堆。例子2:PriorityQueue,就是堆,可以设置大小比较的Comparator,从而变成小顶堆或者大顶堆。如果面试官不要求实现具体的堆代码,可以简略使用这个封装的数据结构。例子3:之前在研究定时任务时,发现Java最原始的Timer,对定时任务进行时间排序时,使用的就是小顶堆。

2、在腾讯、字节、阿里等面试中,都考到了不止1次。

最小堆基本概念

最小堆和最大堆,都是一样的,这里以最小堆为例。

2个属性:数据结构是完全二叉树、父节点存储的值≤子节点存储的值3个操作:“创建”、“插入”、“弹出堆顶元素”。

完全二叉树:如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。

完全二叉树

也就是说,完全二叉树:

至少要有k的深度:那么k深度至少要有1个节点编号要和满二叉树一样:那么k-1节点都是满的,且k层的节点都聚集在左侧

由于向左紧凑排列,于是我们可以用数组表示完全二叉树,中间没有空隙:

数组表示完全二叉树

同时还可以得到2个重要性质:

左右子树的坐标,用数组坐标表示为2N+1、2N+2父亲节点的坐标,用数组坐标表示为(N-1)/2

这样当需要回溯父节点,或者遍历左右子树时,就不需要指针了。

最小堆创建

总共2步,也就是满足最小堆的2个属性:

1、创建完全二叉树

2、从最后一个父节点开始,遍历所有节点,交换顺序使其满足“父节点值≤子节点值”

对于第1步,用数组来做,很方便,只需要放进数组中就行了。如果题目给的是数组,直接就复制一下即可;如果给的是树,则中序遍历(根、左、右)一次即可。

对于第2步,我们从最后一个父节点开始,倒着往前交换顺序。为什么要倒着?正着也可以的,只是倒着处理更好理解。

(1)最后节点坐标index=9,父节点坐标(9-1)/2=4,31<60,不用交换

(2)遍历倒数第2个父节点,此时父节点的坐标为上次父节点坐标4-1=3。找到左右子女较小的数,为18。然后发现18<44,于是将18和44进行交换。由于44下沉,可能影响子树,需要递归修复子树,44是叶子节点没有子树,结束。

(3)3-1=2,23和20进行交换。注意20是右侧子树,因为是倒着遍历的。

(4)2-1=1,此时左侧88>18,88和18交换,由于88>44,继续下沉,88和44交换。

(5)1-1=0,最后一次,此时67>18,交换;67>31,交换;67>60,交换。

有时候会容易混淆,最小堆的目的是找出“最小”的,而不是二叉排序树,所以左右子树的值是没有固定大小关系的。

最小堆插入

1、把新元素安排在最后

2、自底向上递归调整

(1)插入15到最后

(2)15<60,上浮;15<31,上浮;15<18,上浮,完成。

这里可能会有疑问:如果调整了父节点,那需不需要递归调整另外一个子树的数据呢?当然不需要,因为最小堆已经构建好了,一旦发生调整,当前值就是左右子树的最小值。

举个例子:

插入15后,如果15和60发生调整,那么左侧的值,一定也小于15,不需要调整,左侧67<60<15。同样,上浮后,15<31,那么左侧44一定小于15,44<31<15,不需要调整。最小堆弹出堆顶元素

1、取得堆顶元素,将最后一个元素替换堆顶元素

2、从堆顶开始自顶向下递归调整

(1)我们删除掉刚刚插入的15,然后把末尾的60放在15的位置

(2)自顶向下,递归比较,60>18,交换;60>31,交换;60<67,不处理,完成。

本题解析

有很多类似的考题,比如腾讯之前的“从1亿个QQ号中找出最小的10个QQ号”,都是类似的题目。

1、内存够用的情况下:

(1)排序:背不了快排,至少写个冒泡吧。时间O(NlogN),空间O(logN)

(2)最小堆:直接全部排序,最小堆。时间O(NlogN),每次插删logN,N次插入。空间O(N)

(3)快排思想:利用快排思想找第k小的数,然后左侧的就是小于k的。时间O(N),空间O(logN)

2、内存不够用的情况下:

只能最大堆:

(1)构建最大堆-k

(2)剩余的数据依次输入

如果值≥堆顶值,说明一定不会是最小k个值之一,丢弃。如果值<堆顶值,说明它可能会是最小k个值之一,移除堆顶值,把当前值放进来。

最终代码:

import java.util.Arrays;class Solution2 {    public int[] smallestK(int[] arr, int k) {        if (arr == null || arr.length < k) {            return arr;        }        if (k <= 0) {            return new int[0];        }        BinHeap heap = new BinHeap();        heap.init(arr, k, false);        for (int i = k; i < arr.length; i++) {            if (arr[i] > heap.top()) {                continue;            }            heap.delete();            heap.insert(arr[i]);        }        return heap.heap();    }    public static class BinHeap {        private int[] heap;        private int size;        private boolean smallBinHeap;        public boolean matched(int a, int b) {            return smallBinHeap ? a < b : a > b;        }        public void init(int[] arr, int k, boolean smallBinHeap) {            if (arr == null || arr.length < k) {                throw new IllegalArgumentException("bad args");            }            heap = Arrays.copyOf(arr, k);            size = k;            this.smallBinHeap = smallBinHeap;            int parentIdx = ((size - 1) - 1) / 2;            while (parentIdx >= 0) {                fixDown(parentIdx);                parentIdx -= 1;            }        }        public void insert(int val) {            if (heap.length <= size) {                heap = Arrays.copyOf(heap, size * 2);            }            heap[size] = val;            size++;            fixUp(size - 1);        }        public int delete() {            int top = heap[0];            heap[0] = heap[size - 1];            size--;            fixDown(0);            return top;        }        public int top() {            return heap[0];        }        public int[] heap() {            return Arrays.copyOf(heap, size);        }        private void fixDown(int idx) {            while (idx < size) {                int toSwapIdx = findChildIdx(idx);                if (toSwapIdx == -1) {                    break;                }                if (matched(heap[idx], heap[toSwapIdx])) {                    break;                }                int temp = heap[toSwapIdx];                heap[toSwapIdx] = heap[idx];                heap[idx] = temp;                idx = toSwapIdx;            }        }        private void fixUp(int idx) {            while (idx > 0) {                int parentIdx = (idx - 1) / 2;                if (matched(heap[parentIdx], heap[idx])) {                    break;                }                int temp = heap[idx];                heap[idx] = heap[parentIdx];                heap[parentIdx] = temp;                idx = parentIdx;            }        }        private int findChildIdx(int parentIdx) {            int leftIdx = parentIdx * 2 + 1;            int rightIdx = parentIdx * 2 + 2;            if (leftIdx >= size) {                return -1;            }            if (rightIdx >= size) {                return leftIdx;            }            return matched(heap[leftIdx], heap[rightIdx]) ? leftIdx : rightIdx;        }        public void print() {            System.out.print("size=" + size + ": ");            for (int i = 0; i < size; i++) {                System.out.print(heap[i] + (i < size - 1 ? "," : ""));            }            System.out.println("");        }    }//    public static void main(String[] args) {//        BinHeap heap = new BinHeap();//        int[] arr = new int[] {67, 88, 23, 44, 31, 51, 20, 18, 54, 60};//        heap.init(arr, 10, true);//        heap.print();//        heap.insert(15);//        heap.print();//        heap.delete();//        heap.print();//    }}
扩展

1、如果不用自己写堆,可以尝试使用PriorityQueue,这样就只需要关心主逻辑即可。

        int[] ans = new int[k];        if (k == 0) return ans;        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);        for (int i : arr) {            if (q.size() == k && q.peek() <= i) continue;            if (q.size() == k) q.poll();            q.add(i);        }        for (int i = k - 1; i >= 0; i--) ans[i] = q.poll();        return ans;

2、在一些经典代码中,比如Timer,可以学到很多更高级的写法。比如Timer,乘以2变为了左移1,条件判断也很简单。

但是在面试中,不要去强求写得漂亮,而是至少需要根据自己的逻辑能写出来。

    /**     * Establishes the heap invariant (described above) in the subtree     * rooted at k, which is assumed to satisfy the heap invariant except     * possibly for node k itself (which may have a nextExecutionTime greater     * than its children's).     *     * This method functions by "demoting" queue[k] down the hierarchy     * (by swapping it with its smaller child) repeatedly until queue[k]'s     * nextExecutionTime is less than or equal to those of its children.     */    private void fixDown(int k) {        int j;        while ((j = k << 1) <= size && j > 0) {            if (j < size &&                queue[j].nextExecutionTime > queue[j+1].nextExecutionTime)                j++; // j indexes smallest kid            if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)                break;            TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;            k = j;        }    }
结束语

能看到这里的你,一定是个热爱编程的同学。如果想要有计划地准备大厂面试,欢迎关注。

关注我,带你像准备高考一样有计划地准备大厂面试!(当前:2022年第5周)

周一:新闻动态——了解岗位要求、薪资,找到目标

周二:编程刷题——高频算法面试题

周三:专业真题——高频连环炮提问

周四:面试提问——HR面的问题如何回答

周五:热门推荐——高效工具

标签: #关于堆的判断