- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我正在使用 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
对于降序,我尝试了以下不同的方法,但它们都有一些缺点:
使用负值作为优先级进行反向排序。我必须使用单独的列表来使数据可重用。如果原始列表很大,则复制列表的成本很高。
>>> 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
优先使用负值元组,这也是浪费空间。我不想将整数列表存储为元组列表。
>>> 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 中缺少使用键排序。像这样的东西:
>>> 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。喜欢:
>>> 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
有什么方法可以获得与升序订单类似的降序订单吗? :)
最佳答案
正如我们在评论中所讨论的那样,当您从空堆开始并在进行中添加值时,您对使用负值将最小堆翻转为最大堆时复制数据的担忧无关紧要.由于这是查找值流的运行中位数的用例,因此在添加值时取反值应该可以正常工作。
这是我编写的运行中值生成器,只是为了仔细检查它是否按我预期的方式工作:
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
堆存储小于或等于中值的值。每个值在被压入时都会被取反,因此对它使用正常的最小堆操作可以使它像最大堆一样工作。我们只需要记住重新否定我们从中取出的任何值,回到原来的符号。
关于python - 使用 heapq 降序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44792566/
序 大家好呀,我是summo,这次来写写我在上班空闲(摸鱼)的时候做的一个小网站的事。去年阿里云不是推出了个活动嘛,2核2G的云服务器一年只要99块钱,懂行的人应该知道这个价格在业界已经是非常良心了
我尝试根据给定的级别顺序(BFS 顺序)构造 BST。我知道这是可能的,但我不知道我该怎么写。问题是我必须使用 BFS 序列。所以,我不能在这里使用递归,我必须迭代地编写我的程序......我发现这有
我是一名优秀的程序员,十分优秀!