题目定位
维护一个大小为 k 的小根堆，就等于维护了当前 top-k 前沿，而堆顶天然就是第 k 大元素。
关键观察
你并不需要完整排序，只需要记住目前见过的前 k 大元素。
目标复杂度
O(n log k) / O(k)
这题的解法思路怎么拆
1
维护一个大小为 k 的小根堆，就等于维护了当前 top-k 前沿，而堆顶天然就是第 k 大元素。
2
你并不需要完整排序，只需要记住目前见过的前 k 大元素。
3
先用一句话说明堆顶代表什么。
4
新候选者一旦合格就立刻入堆。
参考实现
Python# Generic pattern template
import heapq
heap = []
heapq.heappush(heap, value)
smallest = heapq.heappop(heap)
# max heap in Python
heapq.heappush(heap, -value)
largest = -heapq.heappop(heap)
常见坑点
warning
明明小根堆维护 k 个元素更自然，却写成大根堆弹 k 次。
warning
堆大小超过 k 还不及时修正。
高频追问
和 quickselect 相比，这种方法优劣如何？
为什么堆顶是第 k 大，而不是最大值？
继续刷相关题
先把 堆 / 优先队列 这个模式刷成体系，再去做更难变体。