wrc's Wiki

更改

Heap (查看源代码)

2022年10月8日 (六) 13:48的版本

添加207字节 、 2022年10月8日 (六) 13:48
无编辑摘要
第4行： 第4行：  
* pop：O(log n)
 
* pop：O(log n)
   −
== 找前 ''n'' 大的数 ==
+
== 找前 ''n'' 大的数（top K） ==
   −
参考 Python 的实现：https://github.com/python/cpython/blob/3.9/Lib/heapq.py#L521
+
* 先 push ''n'' 个元素到小根堆中（找前 ''n'' 小则用大跟堆）
 +
* 对剩下的元素，和堆顶比较，'''若更大'''则替换堆顶
   −
* 先 push ''n'' 个元素到小根堆中（找前 ''n'' 小则用大跟堆）
+
<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:刷题]]
取自“https://wiki.ruo-chen.wang/wiki/特殊:移动版差异/538”