python - 使用 heapq 降序

Question

我正在使用 Python 的 heapq 模块按升序和降序获取数据。

对于升序，我使用的是最小堆，它运行良好，如下所示:

>>> from heapq import heapify, heappop
>>> heap = [9, 3, 1, 5, 6, 2, 7]
>>> heapify(heap)
>>> heappop(heap)
1
>>> heappop(heap)
2
>>> heappop(heap)
3

对于降序，我尝试了以下不同的方法，但它们都有一些缺点:

1. 使用负值作为优先级进行反向排序。我必须使用单独的列表来使数据可重用。如果原始列表很大，则复制列表的成本很高。

   >>> from heapq import heapify, heappop
   >>> heap = [9, 3, 1, 5, 6, 2, 7]
   >>> heap_neg = [-x for x in heap]
   >>> heapify(heap_neg)
   >>> -heappop(heap_neg)
   9
   >>> -heappop(heap_neg)
   7
   >>> -heappop(heap_neg)
   6
   

2. 优先使用负值元组，这也是浪费空间。我不想将整数列表存储为元组列表。

   >>> from heapq import heapify, heappop
   >>> heap = [(-9, 9), (-3, 3), (-1, 1), (-5, 5), (-6, 6), (-2,2), (-7,7)]
   >>> heapify(heap)
   >>> heappop(heap)[1]
   9
   >>> heappop(heap)[1]
   7
   >>> heappop(heap)[1]
   6
   

3. 在 heapify 中缺少使用键排序。像这样的东西:

   >>> from heapq import heapify, heappop
   >>> heap = [9, 3, 1, 5, 6, 2, 7]
   >>> heapify(heap, key=lambda x:-x) # This doesn't work as heapify don't have key parameter
   

4. 如果我使用 heapq._heapify_max(heap)，我将必须在每个元素弹出后进行 _heapify_max。喜欢:

   >>> from heapq import _heapify_max, heappop
   >>> heap = [9, 3, 1, 5, 6, 2, 7]
   >>> _heapify_max(heap)
   >>> heappop(heap)
   9
   >>> heappop(heap)  # popping without _heapify_max gives wrong result
   1
   >>> _heapify_max(heap)
   >>> heappop(heap) # popping after _heapify_max gives correct result
   7
   

有什么方法可以获得与升序订单类似的降序订单吗？ :)

Answer 1

正如我们在评论中所讨论的那样，当您从空堆开始并在进行中添加值时，您对使用负值将最小堆翻转为最大堆时复制数据的担忧无关紧要.由于这是查找值流的运行中位数的用例，因此在添加值时取反值应该可以正常工作。

这是我编写的运行中值生成器，只是为了仔细检查它是否按我预期的方式工作:

def running_median(iterable):
    left_q = [] # heap of smaller-than-median elements, stored negated
    right_q = [] # heap of larger-than-median elements

    for value in iterable:
        if len(left_q) == len(right_q): # push to left_q when they're equal size
            if len(right_q) > 0 and value > right_q[0]:
                value = heapq.heapreplace(right_q, value)
            heapq.heappush(left_q, -value)
        else: # push to right_q only when it's (strictly) smaller
            if value < -left_q[0]:
                value = -heapq.heapreplace(left_q, -value)
            heapq.heappush(right_q, value)

        # len(left_q) is always >= len(right_q) so we never yield right_q[0]
        if len(left_q) > len(right_q):
            yield -left_q[0]
        else:
            yield (-left_q[0] + right_q[0]) / 2

left_q 堆存储小于或等于中值的值。每个值在被压入时都会被取反，因此对它使用正常的最小堆操作可以使它像最大堆一样工作。我们只需要记住重新否定我们从中取出的任何值，回到原来的符号。