“Heap”的版本间的差异
跳到导航
跳到搜索
| 第9行： | 第9行： | ||
* 对剩下的元素，和堆顶比较，'''若更大'''则替换堆顶 | * 对剩下的元素，和堆顶比较，'''若更大'''则替换堆顶 | ||
| + | 时间复杂度 O(n logk)。 | ||
<syntaxhighlight lang=python> | <syntaxhighlight lang=python> | ||
def topk(xs: list[int], k: int): | def topk(xs: list[int], k: int): | ||
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