headpq - Top-K问题

python库

heapq是通过堆排序来实现的。

heapq.nlargest()

返回由iterable中最大的n个元素组成的列表， 等价于：sorted(iterable, key=key, reverse=True)[:n]

heapq.nlargest(n, iterable, key=None)

• key： 比较函数

heapq.nsmallest()

返回iterable中最小的n个元素组成的列表， 等价于sorted(iterable, key=key)[:n]

heapq.nsmallest(n, iterable, key=None)

小节

当要查找的元素个数相对比较小的时候,函数 nlargest() 和 nsmallest() 是很合适的。如果你仅仅想查找唯一的最小或最大(N=1)的元素的话,那么使用 min() 和max() 函数会更快些。类似的,如果 N 的大小和集合大小接近的时候,通常先排序这个集合然后再使用切片操作会更快点(sorted(items)[:N] 或者是 sorted(items)[-N:])。

heapq.heapify()

将列表x转化为一个堆。堆数据结构最重要的特征是 heap[0] 永远是最小的元素。

heapq.heapify(x)

heapq.heappop()

取出并返回堆（heap）中最小的元素， 并将剩余的元素组织成堆。
如果heap为空， 则IndexError被触发。

heapq.heappop(heap)

• heap: 堆对象

heapq.heappush()

heapq.heapreplace

heapq.merge