使用heapq降序 [英] Descending order using heapq

问题描述

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

I am using heapq module of Python get data in ascending and descending order.

对于升序，我使用的是最小堆，它的工作原理如下:

For ascending, I am using min heap and it works well as follow:

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

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

For descending, I have tried following different approaches but all of them have some drawback:

1. 使用负值作为获得反向排序的优先级.我必须使用单独的列表来使数据可重用.如果原始列表很大，那么拥有列表副本会很昂贵.

1. Using negative value as the priorirty to get reverse sort. I have to use separate list to make data reusable. If the original list is big, having copy of list is costly.

>>> 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

使用具有负值的元组作为优先级，这也浪费了空间.我不想将整数列表存储为元组列表.

Using tuple with negative value as priority, this is also waste of space. I would not like to store list of ints as list of tuples.

>>> 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

缺少用于在heapify中排序的键.像这样:

Using key to sort in heapify is missing. Something like:

>>> 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

如果我使用heapq._heapify_max(heap)，则每个元素弹出后我都必须_heapify_max.喜欢:

If I use, heapq._heapify_max(heap), I will have to _heapify_max after each element pop. Like:

>>> 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

有什么方法可以使我获得降序订单，与获得升序订单的方式类似吗? :)

Is there any way I can get descending order similar to how I got ascending order? :)

推荐答案

正如我们在评论中所讨论的，当您使用负值将最小堆翻转为最大堆时，您对复制数据的担忧与您无关从一个空堆开始，然后随便添加值.由于这是查找值流的运行中值的用例，因此在添加值时取反就可以了.

As we discussed in the comments, your concerns about copying data when using negated values to flip a min-heap into a max-heap don't matter when you're starting with an empty heap and adding the values as you go. Since that's the use case when finding the running median of a stream of values, negating the values as you add them should work just fine.

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

Here's a running median generator I wrote just to double check that it works the way I expected:

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堆存储小于或等于中值的值.推入每个值时会取反，因此对它使用常规的min-heap操作会使它像max-heap一样工作.我们只需要记住重新取回我们从中获得的任何值，即可返回到原始符号.

The left_q heap stores the less-than-or-equal-to-median values. Each value is negated when it's pushed, so using the normal min-heap operations on it makes it work like a max-heap. We just need to remember to re-negate any value we take out of it, to get back to the original sign.

这篇关于使用heapq降序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！