Python包含了用于min-堆的heapq模块,但我需要一个max堆。在Python中我应该使用什么来实现最大堆?


当前回答

我创建了一个名为heap_class的包,它实现了最大堆,还将各种堆函数包装到一个与列表兼容的环境中。

>>> from heap_class import Heap
>>> h = Heap([3, 1, 9, 20], max=True)
>>> h.pop()
20
>>> h.peek()  # same as h[0]
9
>>> h.push(17)  # or h.append(17)
>>> h[0]  # same as h.peek()
17
>>> h[1]  # inefficient, but works
9

从最大堆中获得最小堆。

>>> y = reversed(h)
>>> y.peek()
1
>>> y  # repr is inefficient, but correct
Heap([1, 3, 9, 17], max=False)
>>> 9 in y
True
>>> y.raw()  # underlying heap structure
[1, 3, 17, 9]

正如其他人所提到的,在max堆中处理字符串和复杂对象在heapq中是相当困难的,因为它们不同 否定的形式。heap_class实现简单:

>>> h = Heap(('aa', 4), ('aa', 5), ('zz', 2), ('zz', 1), max=True)
>>> h.pop()
('zz', 2)

支持自定义键,并与后续的推/追加和弹出一起工作:

>>> vals = [('Adam', 'Smith'), ('Zeta', 'Jones')]
>>> h = Heap(vals, key=lambda name: name[1])
>>> h.peek()  # Jones comes before Smith
('Zeta', 'Jones')
>>> h.push(('Aaron', 'Allen'))
>>> h.peek()
('Aaron', 'Allen')

(实现是建立在heapq函数上的,所以它都是用C语言或C语言包装的,除了Python中max heap上的heappush和heapreplace)

其他回答

允许您选择任意数量的最大或最小的项目

import heapq
heap = [23, 7, -4, 18, 23, 42, 37, 2, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
heapq.heapify(heap)
print(heapq.nlargest(3, heap))  # [42, 42, 37]
print(heapq.nsmallest(3, heap)) # [-4, -4, 2]

最简单的方法 就是把每个元素都转换成负数,问题就解决了。

import heapq
heap = []
heapq.heappush(heap, 1*(-1))
heapq.heappush(heap, 10*(-1))
heapq.heappush(heap, 20*(-1))
print(heap)

输出如下所示:

[-20, -1, -10]

你可以使用

import heapq
listForTree = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]    
heapq.heapify(listForTree)             # for a min heap
heapq._heapify_max(listForTree)        # for a maxheap!!

如果你想要弹出元素,使用:

heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap

最简单最理想的解决方案

将这些值乘以-1

好了。所有最高的数字现在都是最低的,反之亦然。

只要记住,当您弹出一个元素与-1相乘以再次获得原始值时。

我还需要使用max-heap,我处理的是整数,所以我只是包装了我需要的heap中的两个方法,如下所示:

import heapq


def heappush(heap, item):
    return heapq.heappush(heap, -item)


def heappop(heap):
    return -heapq.heappop(heap)

然后,我只是分别用heappush()和heappop()替换了我的heapq.heappush()和heappop()调用。