python最大堆，使用topN还是自实现？

Question

python中有heapq，用于一般用途。我想记录topN(0~20)为10e7记录。

如果使用heapq，应该使用“-”将max转换为min；并记录底部的min数，调用heapq.heappushpop()

我应该使用heapq还是自实现堆(可能是buggy还是效率较低)？

#update

import heapq
class TopN(object):
    """
    v format: (num, value)

    after looking into http://hg.python.org/cpython/file/2.7/Lib/heapq.py, 
    i find heappushpop already optimize, no need bottom value

    feed() can be optimize further, if needed:
        using func object instead of compare len(self.h) each time
    """
    def __init__(self, N):
        self.N = N
        self.h = []        

    def feed(self, v):  
        if len(self.h) < self.N:
            heapq.heappush(self.h, v)
        else:
            heapq.heappushpop(self.h, v)

    def result(self):
        self.h.sort(reverse=True)
        return self.h

def t_topn():
    topn = TopN(10)
    for i in xrange(5):
        topn.feed((i, str(i)))
    res = topn.result()    
    assert sorted(res, reverse=True) == res 

def t_topn_random():
    import random
    topn = TopN(10)
    for i in xrange(100):
        x = random.randint(0, 1e4)
        topn.feed((x, str(x)))
    res = topn.result()    
    assert sorted(res, reverse=True) == res 

if __name__ == '__main__':
    t_topn()
    t_topn_random()

Answer 1

heapq的唯一问题是它没有像stdlib中的其他所有东西那样提供key函数。(如果你好奇的话，雷蒙德·赫廷格在这封邮件上解释道。他说得对，heapq不能提供与其他排序函数相同的接口--但原因并不影响您的用例，因为key只是lambda x: -x。)

通常的解决办法是装饰-堆-不装饰。也就是说，将值的修改版本放入按key排序的堆中。通常，这意味着以下之一：

• 存储key(x)而不是x，然后访问unkey(value)而不是value (假设key是可逆的)。
• 存储(key(x), x)而不是x，然后访问value[1]。(这可能破坏稳定性，但heapq无论如何也不能保证稳定性。)
• 编写一个实现自定义__le__方法的包装类，然后存储Wrapper(x)而不是x，并访问value.value而不是value。

在您的情况下，关键功能是可逆的。所以，只需存储-x，并访问-value。这和装饰一样琐碎。

不过，不管它有多简单，您可能应该编写一个包装器，否则在某个时候会搞砸它。例如，您可以编写一个maxheap，它将min堆封装在heapq中，如下所示：

import heapq
def heapify(x):
    for i in range(len(x)):
        x[i] = -x[i]
    heapq.heapify(x)
def heappush(heap, item):
    heapq.heappush(heap, -item)
def heappop(heap):
    return -heapq.heappop(heap)

…诸如此类的其他功能。这可能有点痛苦，但它比从头开始实现整个过程要少得多。

您可能需要将堆包装在一个面向对象的API中，这样就可以执行heap.push(x)而不是heapq.heappush(heap, x)等操作。

import heapq
class MaxHeap(object):
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)
    def push(self, value):
        heapq.heappush(self.heap, -value)
    def pop(self):
        return -heapq.heappop(self.heap)

…

如果您快速浏览一下ActiveState的菜谱或PyPI上的模块，您会发现其他人已经为您完成了大部分工作。

或者，您可以将heapq源代码(纯Python)复制并粘贴为maxheapq.py，只需将cmp_lt函数替换为相反的函数即可。(当然，如果要这样做，那么修改cmp_lt从一开始就接受一个key参数，并修改所有其他函数以传递key，这可能同样简单，而且非常清楚--请记住，它将不再像以前那样适用，因为它不能保证key只被调用一次。)

如果你真的想活得危险(你不应该)，你甚至可以把它关起来：

import heapq
def cmp_gt(x, y):
    return y < x if hasattr(y, '__lt__') else not (x <= y)
heapq.cmp_lt = cmp_gt

但你不想用真正的代码去做。