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


当前回答

我实现了一个最大堆版本的heapq,并将它提交给PyPI。(对heapq模块CPython代码的改动很小。)

https://pypi.python.org/pypi/heapq_max/

https://github.com/he-zhe/heapq_max

安装

pip install heapq_max

使用

dr:与heapq模块相同,只是所有函数都增加了' _max '。

heap_max = []                           # creates an empty heap
heappush_max(heap_max, item)            # pushes a new item on the heap
item = heappop_max(heap_max)            # pops the largest item from the heap
item = heap_max[0]                      # largest item on the heap without popping it
heapify_max(x)                          # transforms list into a heap, in-place, in linear time
item = heapreplace_max(heap_max, item)  # pops and returns largest item, and
                                    # adds new item; the heap size is unchanged

其他回答

最简单最理想的解决方案

将这些值乘以-1

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

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

如果你想用max heap得到最大的K元素,你可以做下面的技巧:

nums= [3,2,1,5,6,4]
k = 2  #k being the kth largest element you want to get
heapq.heapify(nums) 
temp = heapq.nlargest(k, nums)
return temp[-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()调用。

我创建了一个名为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)

heapq模块拥有实现maxheap所需的一切。 它只做max-heap的堆推功能。 我已在下面示范如何克服这一点

在heapq模块中添加这个函数:

def _heappush_max(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown_max(heap, 0, len(heap)-1)

最后加上这句话:

try:
    from _heapq import _heappush_max
except ImportError:
    pass

瞧!这是完成了。

PS -转到heapq函数。首先在编辑器中写入“import heapq”,然后右键单击“heapq”并选择转到定义。