高频必考！堆排序：用数组模拟二叉树，空间O(k)拿下第K大-北京尧图网络

LC.215「数组中的第K个最大元素」大厂面试出镜率TOP5。你当然可以Arrays.sort()然后取下标O(nlogn) 能过但面试官会追问“如果n 10⁹内存放不下整个数组怎么办”“如果数据是流式到达的不能回头你怎么办”这时候堆才是正确答案。今天我们用容量k的小顶堆以O(nlogk)时间、O(k)空间解决这个问题——而且堆的底层数组实现的完全二叉树我们一并讲透让你面试时既能写API也能手撕底层。题目速览30 秒读懂给定数组nums和整数k返回数组中第k个最大的元素。示例[3,2,1,5,6,4], k2 → 输出5示例[3,2,3,1,2,4,5,5,6], k4 → 输出4重复元素各占名次约束n ≤ 1e5数值范围±1e4。全局排序能过但面试官期待更优解。核心思路用“最鸡肋的元素”做看门狗暴力思路先排序再取nums[n-k]O(nlogn)。能过但面试官会问“如果n10⁹呢”堆的直觉——为什么是“小顶堆”我们要找的是第k大等价于保留最大的k个数其中最小的那个就是第k大。维护一个容量为k的小顶堆堆里存的是当前见过的“最大的k个数”堆顶是这k个数里最小的也就是最“鸡肋”的遍历每个数如果堆没满 → 直接入堆如果x 堆顶→ 踢掉堆顶它不配留在前k大让 x 入堆如果x ≤ 堆顶→ x连前k大的门槛都够不着直接扔掉遍历结束堆顶就是答案。为什么不用大顶堆大顶堆取最大值容易但容量如果设为k你永远不知道该踢谁——因为你不知道当前最大值是否属于最终的前k大。小顶堆的设计让“最该被踢的”恰好暴露在堆顶。️ 图解算法手把手走一遍nums [3,2,1,5,6,4],k2维护容量2的小顶堆步骤当前元素堆内容堆顶在前动作13[3]堆未满入堆22[2, 3]堆未满入堆后 2 上浮到顶31[2, 3]1 堆顶 2直接扔掉45[3, 5]5 堆顶 2弹出 25 入堆上浮56[5, 6]6 堆顶 3弹出 36 入堆64[5, 6]4 堆顶 5直接扔掉遍历结束堆 {5, 6}堆顶5就是第2大✅️ 堆的底层藏在数组里的完全二叉树堆是一棵完全二叉树用数组存储节点i的左孩子2*i 1节点i的右孩子2*i 2节点i的父节点(i-1)//2两个核心操作上浮sift_up新元素加在数组末尾和父节点比较比父小小顶堆就交换直到合适位置。下沉sift_down堆顶被替换后和孩子中较小的比较大了就交换直到合适位置。建堆为什么是O(n)而不是O(nlogn)自底向上从最后一个非叶节点开始下沉约一半节点是叶子不用动约1/4节点最多下沉1层1/8下沉2层……求和收敛于O(n)。直觉便宜的节点多贵的节点少摊下来线性。代码实现Python手写堆 Java PriorityQueuePython版手写堆面试必备classSolution:deffindKthLargest(self,nums:List[int],k:int)-int:heap[]# 小顶堆defsift_up(i):whilei0:p(i-1)//2ifheap[i]heap[p]:heap[i],heap[p]heap[p],heap[i]ipelse:breakdefsift_down(i,size):while2*i1size:child2*i1ifchild1sizeandheap[child1]heap[child]:child1# 选较小的孩子ifheap[i]heap[child]:heap[i],heap[child]heap[child],heap[i]ichildelse:breakforxinnums:iflen(heap)k:heap.append(x)sift_up(len(heap)-1)elifxheap[0]:heap[0]x sift_down(0,k)returnheap[0]Java版PriorityQueue工程写法classSolution{publicintfindKthLargest(int[]nums,intk){// 小顶堆容量 kPriorityQueueIntegerheapnewPriorityQueue();for(intx:nums){heap.offer(x);if(heap.size()k){heap.poll();// 自动弹出堆顶最小值}}returnheap.peek();}}⚠️防坑提醒Python的heapq默认是小顶堆如果要大顶堆要push-x。Java的PriorityQueue默认小顶堆用Comparator.reverseOrder()变成大顶堆。手写堆时sift_down的循环条件是2*i1 size不是别搞混。⏱️ 复杂度分析面试必问维度堆解法全局排序时间O(nlogk)O(nlogn)空间O(k)O(1)原地排序或O(n)复制当k远小于n时比如k10n1e6堆解法几乎线性而全局排序要处理百万级数据。当数据流式到达时堆更是唯一选择。举一反三3 道高频变种题题目变化点应对策略LC.347 前K个高频元素按频率找Top-K哈希表统计频率堆存(频率, 元素)依然是容量k的小顶堆LC.23 合并K个升序链表多路归并堆存K个链表头每次弹最小值并推入其后继LC.295 数据流的中位数动态找中位数一个大顶堆存较小一半一个小顶堆存较大一半保持堆大小平衡面试追问模拟提前准备Q1为什么第k大要用“小顶堆”而不是大顶堆小顶堆的堆顶是堆里最小的正好是我们想随时“踢掉”的那个。每来一个新数比堆顶大就踢掉堆顶换新人保证堆里始终是“最大的k个数”。如果用大顶堆你无法判断该踢谁。Q2建堆为什么是O(n)能不能一句话讲清楚自底向上建堆时高度为h的节点数量约n/2(h1)下沉代价为h总代价Σh·n/2(h1) O(n)。便宜的节点多贵的高层节点少摊下来线性。Q3Java的PriorityQueue底层是什么线程安全吗底层是动态数组实现的二叉小顶堆offer/poll是O(logn)peek是O(1)。不是线程安全的并发场景用PriorityBlockingQueue。Q4如果数据是流式到达不能一次性拿到全部堆解法还能用吗完全能用。流式场景下堆解法是黄金标准——每个元素来的时候直接处理不需要存储历史数据。这正是它相比“全局排序”的最大优势。实战小技巧刷题党必备口诀第k大小顶堆容量k堆顶就是它。模板凡是“流式Top-K”、“海量数据找最大/最小K 个”优先堆。防溢出Java中用Comparator.reverseOrder()实现大顶堆不要手写(a,b)-b-a可能溢出。实际应用场景不止是刷题任务调度器操作系统按优先级调度进程PriorityQueueDijkstra最短路径每次取距离最近的未访问节点堆优化大数据Top-K统计海量日志中找访问量最高的IP延迟队列按时间戳排序处理到期任务今日思考题如果题目要求找“第k小”堆应该怎么改提示用容量k的大顶堆保留最小的k个数堆顶就是第k小。如果找“前k大”但要求输出排序后的结果堆还能做到吗复杂度是多少

高频必考！堆排序：用数组模拟二叉树，空间O(k)拿下第K大

相关推荐

新模型测试期如何安全接入？从评估集到灰度发布的工程攻略

FPGA实时温湿度显示系统设计与OLED驱动实践

IDA Pro插件开发：TMS320C66X DSP逆向全链路解析

更多资讯

新丰电工证怎么考2026河南最新政策你得知道

之前考的证在外省能不能转过来？建管局的特种工证怎么报名全攻略

外省特种电工证能转过来吗？内部消息来了，寒亭特种电工证怎么考更靠谱

咸阳考电工证报名怎么考？怕考不过白交培训费？官方报名入口这样找！

工地太忙根本没时间复习考试？太原井下电工证包过+郑州报考避坑指南全攻略

铜仁电工证在哪里办理怎么报名电工实操考试怕挂科别慌

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？