数据结构与算法 / 系统课时
用堆维护动态前K个元素
用堆维护动态前K个元素
当元素持续到来、又只关心最大的 K 个或最小的 K 个时,没有必要反复对全部数据排序。关键是维护一个大小不超过 K 的堆,让堆顶始终充当当前答案集合的边界,从而把每次更新压缩到对数时间。
学习目标
- 判断维护前 K 大或前 K 小时应该选择哪种堆
- 用固定容量堆在线处理持续到来的元素
- 分析时间、空间复杂度并识别常见边界错误
堆顶为什么要保存答案边界
求前 K 大时,真正需要快速找到的不是当前最大值,而是“前 K 大中最小的那个”。新元素只有超过这个边界,才有资格进入答案集合。因此应维护一个容量为 K 的小根堆,堆顶就是当前第 K 大候选。
求前 K 小正好相反:需要快速找到“前 K 小中最大的那个”,因此使用大根堆。Python 的 heapq 只提供小根堆,可以把数值取负来模拟大根堆。
判断规则可以记成一句话:保留哪一侧,就用堆顶指向该侧答案中最差的元素。
在线维护前 K 个元素
下面同时维护前 K 大与前 K 小。堆未满时直接加入;堆满后只在新元素优于当前边界时替换堆顶。
import heapq
def top_k_largest(stream, k):
if k <= 0:
return []
heap = []
for value in stream:
if len(heap) < k:
heapq.heappush(heap, value)
elif value > heap[0]:
# 小根堆堆顶是当前前 K 大中的最小值,也就是淘汰边界。
heapq.heapreplace(heap, value)
return sorted(heap, reverse=True)
def top_k_smallest(stream, k):
if k <= 0:
return []
heap = []
for value in stream:
if len(heap) < k:
heapq.heappush(heap, -value)
elif value < -heap[0]:
# 取负后堆顶对应当前前 K 小中的最大值。
heapq.heapreplace(heap, -value)
return sorted(-value for value in heap)
if __name__ == "__main__":
numbers = [5, 1, 9, 3, 14, 7, 12]
print(top_k_largest(numbers, 3))
print(top_k_smallest(numbers, 3))预期输出
[14, 12, 9]
[1, 3, 5]用不变量检查算法是否正确
处理任意前缀后,都应该满足两个条件:堆大小不超过 K;堆中保存的是这个前缀内最符合要求的 K 个元素。如果堆已满,新值又没有越过堆顶边界,它不可能进入最终答案,所以可以直接丢弃。
以求前 3 大为例,当前堆保存 5、9、14 时,堆顶是 5。随后读到 7,因为 7 > 5,应淘汰 5;若读到 3,因为 3 <= 5,它不可能属于当前前 3 大,可以忽略。
复杂度与常见边界
设数据总量为 N。每个元素最多进行一次堆插入或替换,堆大小始终不超过 K,因此主体时间复杂度为 O(N log K),额外空间复杂度为 O(K)。如果最终还要把 K 个结果排序,需要额外 O(K log K) 时间。
当 K = 1 时,问题退化为维护最大值或最小值;当 K 大于数据量时,堆最终保存全部元素。实际题目还要确认重复值是否允许计入 K 个位置,以及要求的是“第 K 大元素”还是“去重后的第 K 大不同元素”,两者不能混用同一套计数逻辑。
固定容量堆的核心不是“堆能排序”,而是它能以 O(log K) 的代价持续维护一个淘汰边界。看到数据流、Top K、第 K 大、第 K 小或只需保留少量最佳候选时,应优先检查这种模式。