“Heap”的版本间的差异
跳到导航
跳到搜索
（建立内容为“== 找前 ''n'' 大的数 == 参考 Python 的实现：https://github.com/python/cpython/blob/3.9/Lib/heapq.py#L521 * 先 push ''n'' 个元素到小根堆中（…”的新页面） |
|||
| （未显示同一用户的2个中间版本） | |||
| 第1行： | 第1行： | ||
| − | == | + | == 时间复杂度 == |
| − | + | * push：最坏 O(log n)，平均 O(1) | |
| + | * pop：O(log n) | ||
| + | |||
| + | == 找前 ''n'' 大的数（top K） == | ||
* 先 push ''n'' 个元素到小根堆中（找前 ''n'' 小则用大跟堆） | * 先 push ''n'' 个元素到小根堆中（找前 ''n'' 小则用大跟堆） | ||
| − | * | + | * 对剩下的元素，和堆顶比较，'''若更大'''则替换堆顶 |
| + | |||
| + | 时间复杂度 O(n logk)。 | ||
| + | <syntaxhighlight lang=python> | ||
| + | def topk(xs: list[int], k: int): | ||
| + | heap = [] | ||
| + | for x in xs: | ||
| + | if len(heap) >= k: | ||
| + | if x > heap[0]: | ||
| + | heapq.heapreplace(heap, x) | ||
| + | else: | ||
| + | heapq.heappush(heap, x) | ||
| + | return heap | ||
| + | </syntaxhighlight> | ||
[[Category:刷题]] | [[Category:刷题]] | ||
2022年10月8日 (六) 13:49的最新版本
时间复杂度
- push：最坏 O(log n)，平均 O(1)
- pop：O(log n)
找前 n 大的数（top K）
- 先 push n 个元素到小根堆中（找前 n 小则用大跟堆）
- 对剩下的元素，和堆顶比较，若更大则替换堆顶
时间复杂度 O(n logk)。
def topk(xs: list[int], k: int):
heap = []
for x in xs:
if len(heap) >= k:
if x > heap[0]:
heapq.heapreplace(heap, x)
else:
heapq.heappush(heap, x)
return heap