巧用小顶堆求解第 K 大元素，两道经典题一通百通

🔖 标签：# 算法 #堆结构 #C++ #面试题 #数据结构

Bilibili 同步视频

巧用小顶堆求解第 K 大元素，两道经典题一通百通✨

一、前言💡

在算法刷题与面试场景中，求解数组 / 数据流中的第 K 大元素，是一道出镜率极高的经典题型。不少初学者面对该问题时，常会陷入全量排序、暴力遍历的低效思路中。实则借助小顶堆这一精巧的数据结构，便可化繁为简、四两拨千斤。本文将由浅入深拆解解题逻辑、推演执行流程、附上完整 C++ 代码，并辅以图文演示原理，带你彻底吃透这两道同源考题。

二、核心思路剖析📜

世间算法，万变不离其宗。两道看似独立的题目 ——数据流中的第 K 大元素与数组中的第 K 大元素，内核逻辑高度趋同，皆可依托小顶堆实现高效求解。

2.1 逻辑推演

设我们需要筛选出一组数据里排名前K KK的大数：

1. 若某元素想要跻身前 K 大序列，其数值必须大于当前前 K 个元素里的最小值；

2. 一旦新元素达标，便淘汰原有 K 个元素中的最小值，完成一轮更新迭代；

3. 为了实时、快速获取当前 K 个元素的最小值，小顶堆便是最优选择。

小顶堆特性：堆顶永远是整个堆结构中的最小值，查询、弹出堆顶元素的时间复杂度极低。

📌 总结要义：
以容量为 K 的小顶堆维护全局前 K 大元素，堆内留存当前筛选出的 K 个大数，堆顶即为整组数据的第 K 大元素。谁数值更小，便被优先移出堆外，恰似择优留强、汰弱留庸。

2.2 文字图示演示（Plain Text）

初始状态：空堆，设定 K = 3

堆结构：[ 空 ] 目标：筛选前3大元素，最终堆顶为第3大元素

步骤 1：依次压入前 3 个元素 [9, 7, 8]，堆满（size = 3）

小顶堆自动调整结构，堆顶为最小值7

7 ← 堆顶（当前前3大最小值） / 9 8 堆内元素：{7,9,8}

步骤 2：新增元素 10，入堆后堆 size = 4 > K=3

堆顶最小值7被弹出，重新调整堆结构，新堆顶为8

8 ← 新堆顶 / 9 10 堆内元素：{8,9,10}

步骤 3：新增元素 6，入堆后堆 size = 4 > K=3

堆顶最小值6被弹出，堆结构不变

8 ← 堆顶（最终第3大元素） / 9 10

全程可见：无论元素如何新增更替，堆内始终保留当前前 K 大元素，堆顶就是我们所求的第 K 大元素。

三、复杂度分析⚙️

设数据总个数为n nn，限定堆容量为K KK：

1. 时间复杂度：每个元素入堆、堆调整操作耗时O ( l o g K ) O(log K)O(logK)，整体总复杂度为O ( n l o g K ) O(nlog K)O(nlogK)；
   对比全量排序O ( n l o g n ) O(nlog n)O(nlogn)，当K l l n K ll nKlln时，效率提升十分显著。

2. 空间复杂度：仅开辟大小为K KK的堆空间，复杂度为O ( K ) O(K)O(K)，内存占用极小。

四、C++ 代码实现💻

C++ 标准库中，默认优先队列priority_queue为大顶堆，我们可通过仿函数greater<int>改造为小顶堆，适配本题需求。

4.1 解法一：数组中的第 K 大元素

适用于一次性给定完整数组，直接求解第 K 大元素场景。

#include<iostream>#include<vector>#include<queue>// 优先队列（堆）头文件usingnamespacestd;// 查找数组中第 K 大元素intfindKthLargest(vector<int>&nums,intk){// 定义小顶堆：priority_queue<数据类型, 底层容器, 比较规则>priority_queue<int,vector<int>,greater<int>>minHeap;// 遍历所有元素，逐个入堆for(intnum:nums){minHeap.push(num);// 堆容量超过 K，弹出堆顶最小值if(minHeap.size()>k){minHeap.pop();}}// 最终堆顶即为第 K 大元素returnminHeap.top();}intmain(){vector<int>arr={3,2,1,5,6,4};intk=2;intres=findKthLargest(arr,k);cout<<"数组中第"<<k<<"大元素为："<<res<<endl;return0;}

4.2 解法二：数据流中的第 K 大元素

适用于动态持续流入数据的场景，支持不断添加新数值，实时查询第 K 大元素。

#include<iostream>#include<vector>#include<queue>usingnamespacestd;classKthLargest{private:intk;// 小顶堆，维护前 K 大元素priority_queue<int,vector<int>,greater<int>>minHeap;public:// 构造函数：初始化 K 值与初始数据流KthLargest(intk_val,vector<int>&nums){k=k_val;for(intnum:nums){minHeap.push(num);if(minHeap.size()>k){minHeap.pop();}}}// 新增数据流元素，并返回当前第 K 大元素intadd(intval){minHeap.push(val);if(minHeap.size()>k){minHeap.pop();}returnminHeap.top();}};intmain(){vector<int>stream={4,5,8,2};intk=3;KthLargestkthLargest(k,stream);// 动态添加元素并输出结果cout<<kthLargest.add(3)<<endl;cout<<kthLargest.add(5)<<endl;cout<<kthLargest.add(10)<<endl;return0;}

代码解读📝

1. priority_queue<int, vector<int>, greater<int>>：第三参数greater<int>是构建小顶堆的核心，堆顶始终为最小值；

2. 元素入堆后强制校验堆大小，一旦超出K KK，立即弹出堆顶最小值，保证堆内永远只留存前 K 大元素；

3. 数据流版本将逻辑封装为类，构造函数初始化初始数据，add方法响应动态新增数据，贴合真实业务场景。

五、总结与刷题建议📝

纵观两道同源题型，小顶堆 + 固定容量 K是贯穿始终的核心解法，思路一脉相承：
以小顶堆作 “筛选容器”，守 K 位、汰小值，堆顶定论答案。此思路摒弃了全量排序的冗余操作，时空表现俱佳，也是面试中面试官尤为青睐的解法。

✅ 刷题建议：

1. 先理解堆的底层特性，分清大顶堆、小顶堆的使用场景；

2. 亲手调试上述两份代码，观察堆内元素变化，对照前文图示加深理解；

3. 前往力扣平台找到对应原题独立编写代码，巩固思路，做到提笔即写、思路通透。

算法学习非一日之功，吃透一类题型、掌握一种思想，便可举一反三，从容应对同类变式考题。