题目描述
《Leetcode，面试题17.14，最小k个数》
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
- 0 <= len(arr) <= 100000
- 0 <= 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面的问题如何回答
周五：热门推荐——高效工具