前言:
此时同学们对“关于堆的判断”大致比较着重,大家都想要了解一些“关于堆的判断”的相关内容。那么小编在网摘上收集了一些关于“关于堆的判断””的相关内容,希望我们能喜欢,咱们一起来学习一下吧!题目描述
《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面的问题如何回答
周五:热门推荐——高效工具
标签: #关于堆的判断