题目重点：小顶堆保留最大的K个位置值，重复值照计并说明排序输出成本。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 电影排序TopK变体未给score定义，练习将每条movie score映射到排名键并保留movieId；不把它误当词频TopK。输出需确认是记录、ID或分数。
- 训练每个输入位置可选一次，重复数值保留，k∈[0,n]；输出值按降序。
- 不要求distinct最大值，空数组只有k=0合法，输入有限批次。
解题路线
- 记录TopK使用(score,tieKey)比较键，堆里保留ID与完整record映射；排序字段缺失时先澄清，不能凭“电影”猜评分/票房/热度。
- 堆未满先push，满后只有当前值>heap最小才replace。堆顶始终是保留项中最小者，因此可淘汰最不值得保留的一项。
- 归纳：处理前缀后heap含该前缀K大位置值（不足K则全部）；新值不大于heap顶不影响K大，超过则替换当前最小保留项即可。
- 最后heap不是排序结果，要sorted(reverse=True)。如果只需要unordered K大集合，可省O(k log k)最终排序，不能把堆内部数组称降序。
- distinct TopK需先去重或独立管理成员数；频率TopK需先Counter，两者都不能无意识加到当前题。
手动走一遍
训练[5,5,1,4]、k=2输出[5,5]，不是[5,4]。k=0不应访问heap[0]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from heapq import heappush,heapreplace
def largest_k(values,k):
if not 0 <= k <= len(values):raise ValueError("k out of range")
if not k:return []
heap=[]
for value in values:
if len(heap)<k:heappush(heap,value)
elif value>heap[0]:heapreplace(heap,value)
return sorted(heap,reverse=True)
复杂度
O(n log(k+1)+k log k)时间、O(k)空间；完全排序O(n log n)，quickselect可期望O(n)但输出排序仍有成本。
易错点与追问
容易失分的边界
- 隐式去重。
- 把频次当排名。
- 堆array当最终排序序列。
继续深挖
- 只找第K大能省哪些输出？
- 流式输入未知长度怎样维护？
- k接近n什么方案更合适？
