在python中寻找倒堆

Question

我想梳理时间序列中的n个最大极端。heapq最适合最大的]

def nlargest(series, n):
    count = 0
    heap = []
    for e in series:
        if count < n:
            count+=1
            hp.heappush(heap, e)
        else:
            # keeps heap size fixed 
            hp.heappushpop(heap,e)  
    ''' note: heap[0] is smallest '''
    return heap

但是n最小呢？请注意，我需要原始系列的一个子集，因此无法进行大堆和反转顺序。我想要的实际上是将比较运算符从gt重载到lt。对python中的重载不太熟悉。

一个不太吸引人的选项（假设数值）将是在插入之前取反该项目，然后取反整个返回堆（返回列表或重新堆取被取反的列表），但这似乎很笨拙，并且不适用于非-具有gt和lt的数字。有什么优雅的解决方案吗？

Answer 1

您可以通过将项目的优先级乘以-1来轻松地'创建'一个反向堆。

因此只需要告诉您nsmallest如何“反转”优先级，并根据需要修饰每个值：

def nsmallest(series, n, invert=lambda x: -1 * x):
    count = 0
    heap = []
    for e in series:
        if count < n:
            count += 1
            hp.heappush(heap, (invert(e), e))
        else:
            # keeps heap size fixed
            hp.heappushpop(heap, (invert(e), e))  
    # note: heap[0][1] is largest, remove inverted priorities
    return [h[1] for h in heap]

请注意，我们使用(invertedpriority, value)元组来保持堆反转。

对于非数值类，您只需提供一个反转函数即可颠倒优先级，它只需要一个简单的键，而不是可读的或任何东西：

alphanumeric_invert = lambda x: [(ord(c) * -1) for c in x] 

但是，您不想使用自己编写的heapq.nsmallest() function，它使用了优化的最大堆实现（它使用了内部的heapq.nsmallest()函数），该函数还向保持排序稳定。并且有一个匹配的_heappop_max()。

Answer 2

使用Python标准库中的heapq.nlargest() function：

heapq.nlargest()

从heapq.nsmallest定义的数据集中返回包含heapq.nsmallest个最小元素的列表。等效于：heapq.nsmallest(n, iterable[, key])