题目描述

《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面的问题如何回答

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