第6章|二分、堆与优先队列

Unit 06 · LeetCode #703

← Unit 05
703
Kth Largest in a StreamHeap · Priority Queue · Data Stream

不必维护全部排名,
只需维护决定答案的那条边界。

大小为K的最小堆保存当前最大的K个元素。堆顶是这K个元素中最小的一个,因此恰好是所有已见元素中的第K大。新值到达时,只需更新这一小块候选。

LeetCode #703 原题内容题面转述、设计接口与复杂度

题目要求

设计一个类,持续维护数据流中按排序顺序计算的第 k 大元素。初始化时给定整数 k 和初始数组 nums;每次调用 add(val) 加入新值,并返回当前全部元素中的第 k 大。

class KthLargest: def __init__( self, k: int, nums: List[int] ): pass def add(self, val: int) -> int: pass

约束

  • 0 ≤ nums.length ≤ 10⁴;
  • 1 ≤ k ≤ nums.length + 1;
  • 数值范围为 [-10⁴,10⁴];
  • add 最多调用 10⁴ 次。

官方示例

KthLargest(3, [4,5,8,2])
add(3) → 4
add(5) → 5
add(10) → 5
add(9) → 8
add(4) → 8
KthLargest(4, [7,7,7,7,8,3])
add(2) → 7
add(10) → 7
add(9) → 7
add(9) → 8

本页主方法

维护大小不超过 k 的最小堆。每次插入后若堆大小超过 k,弹出最小值。初始化可逐个加入,时间 O(n log k);每次 add 为 O(log k),空间 O(k)。

第 K 大

将所有元素按从大到小排列后的第K个位置。重复值需要分别计入,并不是第K个不同值。

Top-K 保留区

堆内始终保存当前最大的K个元素;其他元素已经不可能影响当前第K大边界。

边界堆顶

最小堆堆顶是Top-K中最小者,正好把“前K大”和“其余元素”分开。

数据流

新值持续到达,无法每次重新完整排序;需要支持增量更新并立即返回答案。

1. 第K大与Top-K边界
2. 为什么使用大小K的小根堆
3. 数据流插入与淘汰
4. 不变量、重复值与错误实验
5. Python与真实轨迹
6. 离线第K大迁移
k=3,初始数据 [4,5,8,2]选择应保留的3个最大元素

Top-K 保留区

其余淘汰区

最小堆树视图

heapq数组视图

Top-K尚未确定。
当前边界解释

选出三个最大元素后,其中最小者就是整体第三大。

Top-K 堆不变量 处理完当前数据后,堆中保存最大的K个元素;heap[0]是整体第K大。
降序排名数值所属区域

数据流更新记录

当前k3
堆大小0
当前堆顶—
当前第K大—

核心不变量

堆内所有元素构成当前 Top-K;堆外所有已处理元素都不大于堆顶。

为什么是最小堆

Top-K中最应该被淘汰的是最小者。最小堆让这个边界元素始终位于根,插入新值后可在 O(log k) 内淘汰。

已处理元素4
堆容量K3
本轮新值—
本轮淘汰值—
当前返回值—
完整排序知道全部排名,大小K堆只维护答案所需边界

每次重新排序会维护大量不会被查询的排名信息;最小堆只保存前K大及其中最小边界。

三个误区会破坏Top-K语义

堆的方向、容量以及“第K大是否去重”都必须由题目定义推导。

误用大小K的最大堆

堆顶会是第一大;超容量时弹出堆顶反而删除最重要的最大元素。

堆大小不限制为K

若保留所有元素,最小堆顶是整体最小值,不再是第K大。

把重复值去重

第K大按排序位置计数。示例中的多个7和9都必须分别保留。

初始化不足K个元素时,add后仍必须形成K个候选

题目保证 k ≤ nums.length + 1,因此即使初始数组只有K−1个元素,第一次add后也有足够元素返回第K大。

k=1
堆只保留当前最大值
堆顶=第一大
nums长度=k−1
第一次add后
堆大小达到k
重复值[7,7,7,8]
k=3
第三大仍是7
补全LeetCode提交代码大小K的最小堆
class KthLargest:
def __init__(self, k, nums):
self.k =
self.heap = []
for value in nums:
def add(self, val):
if len(self.heap) > self.k:
return
提示 1|类状态:保存 k,并维护一个最小堆。 提示 2|初始化:初始数组与后续数据流应复用同一套 Top-K 更新逻辑。 提示 3|候选更新:新值先进入堆;当容量超过 k 时,淘汰堆内最小值。 提示 4|边界含义:堆大小为 k 时,heap[0] 是 Top-K 中最小者,也就是整体第 k 大。 提示 5|不要依赖堆数组完整有序;heapq 只保证父节点不大于孩子。
更紧的常数优化:当堆已经有K个元素且新值不大于堆顶时,新值不可能进入Top-K,可以直接返回堆顶;也可使用 heappushpop 合并插入与弹出。但基础版本更直接表达不变量。
代码—堆树—Top-K分区—返回值联动官方示例流3,5,10,9,4
1class KthLargest:
2 def __init__(self, k, nums):
3 self.k = k
4 self.heap = []
6 for value in nums:
7 self.add(value)
9 def add(self, val):
10 heapq.heappush(self.heap, val)
12 if len(self.heap) > self.k:
13 heapq.heappop(self.heap)
15 return self.heap[0]
轨迹从初始化后的堆[4,5,8]开始,逐个加入3、5、10、9、4,展示超容量淘汰和返回序列4、5、5、8、8。
完成代码联动后进入离线第K大迁移只有主代码全部正确,或完整播放数据流轨迹后解锁。提示与类状态骨架不计为掌握。
渐进迁移 · LeetCode #215

数组中的第 K 个最大元素

数据从持续到达的流,变成一次性离线数组。变化的是调用方式;不变的是“大小 K 的最小堆保存当前最大的 K 个元素”。

查看官方原题
#215Medium · Array · Heap · Quickselect

题目要求

给定整数数组 nums 和整数 k,返回数组按降序排列后的第 k 大元素。重复值分别占据排名位置,并不是第 k 个不同值。

class Solution: def findKthLargest( self, nums: List[int], k: int ) -> int:

官方示例

nums = [3,2,1,5,6,4], k = 2
输出:5
nums = [3,2,3,1,2,4,5,5,6], k = 4
输出:4

约束与迁移边界

  • 1 ≤ k ≤ nums.length ≤ 10⁵;
  • -10⁴ ≤ nums[i] ≤ 10⁴;
  • 官方追问:能否不进行完整排序;
  • 本单元固定使用大小 k 的最小堆,以复用 #703 的 Top-K 不变量。
#703持续 add(val)每次更新后立即返回
#215一次扫描 nums扫描结束后返回一次
保留集合最大的 K 个元素#703 与 #215 完全相同
边界元素最小堆堆顶Top-K 中最小者 = 第 K 大
更新来源add 调用 → for 扫描动态接口变为离线循环
最终输出每次返回 → 最后返回不变量不变,输出时机变化

按依赖关系排列离线 Top-K 流程

每次点击你认为的下一步;顺序错误会清空当前排列,但不会显示正确答案。

尚未开始

只填写决定不变量的四个语义槽位

这里不要求整段代码记忆,而是确认“容器、扫描、候选更新、答案边界”四个角色。

四个槽位全部正确后显示组装结构。
官方样例轨迹nums=[3,2,1,5,6,4],k=2
0 / 7
当前最小堆[]
本步动作准备扫描
当前边界尚不足 2 个候选
从空堆开始。每读取一个值,都只更新当前 Top-2。

独立重写:大小 K 的最小堆

完整运行官方样例后开放。请独立实现,不提供占位符或完整参考答案。

第6章 Unit 06 Skill卡

你已经把动态数据流中的Top-K边界迁移到离线数组:调用方式改变,但大小K的最小堆、超容量淘汰最小者和heap[0]的排名语义保持不变。

题号与题型#703|数据流Top-K设计
保留集合堆中始终保存当前最大的K个元素
为什么小根堆Top-K中最小者是下一位应淘汰对象
答案位置heap[0]是Top-K最小者,也就是整体第K大
更新流程push新值→若大小>K则pop最小值→返回堆顶
重复值按排名位置计数,不去重
复杂度初始化O(n log k),add O(log k),空间O(k)
常见错误使用最大堆;不限制容量;误以为堆数组完整排序
推荐下一题#215 数组中的第K个最大元素