“Heap”的版本间的差异
跳到导航
跳到搜索
（建立内容为“== 找前 ''n'' 大的数 == 参考 Python 的实现：https://github.com/python/cpython/blob/3.9/Lib/heapq.py#L521 * 先 push ''n'' 个元素到小根堆中（…”的新页面） |
|||
| 第1行： | 第1行： | ||
| + | == 时间复杂度 == | ||
| + | |||
| + | * push：最坏 O(log n)，平均 O(1) | ||
| + | * pop：O(log n) | ||
| + | |||
== 找前 ''n'' 大的数 == | == 找前 ''n'' 大的数 == | ||
2021年7月3日 (六) 07:24的版本
时间复杂度
- push：最坏 O(log n)，平均 O(1)
- pop：O(log n)
找前 n 大的数
参考 Python 的实现：https://github.com/python/cpython/blob/3.9/Lib/heapq.py#L521
- 先 push n 个元素到小根堆中（找前 n 小则用大跟堆）
- 对剩下的元素，和堆顶比较，若更大则替换堆顶