Python包含了用于min-堆的heapq模块,但我需要一个max堆。在Python中我应该使用什么来实现最大堆?
当前回答
arr = [3,4,5,1,2,3,0,7,8,90,67,31,2,5,567]
# max-heap sort will lead the array to assending order
def maxheap(arr,p):
for i in range(len(arr)-p):
if i > 0:
child = i
parent = (i+1)//2 - 1
while arr[child]> arr[parent] and child !=0:
arr[child], arr[parent] = arr[parent], arr[child]
child = parent
parent = (parent+1)//2 -1
def heapsort(arr):
for i in range(len(arr)):
maxheap(arr,i)
arr[0], arr[len(arr)-i-1]=arr[len(arr)-i-1],arr[0]
return arr
print(heapsort(arr))
试试这个
其他回答
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”并选择转到定义。
最简单最理想的解决方案
将这些值乘以-1
好了。所有最高的数字现在都是最低的,反之亦然。
只要记住,当您弹出一个元素与-1相乘以再次获得原始值时。
最简单的方法是反转键的值并使用heapq。例如,将1000.0转换为-1000.0,将5.0转换为-5.0。
我创建了一个名为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)
如果插入的键具有可比性但不像int型,则可能重写它们上的比较操作符(即<=变成>,>变成<=)。否则,您可以重写heapq。heapq模块中的_siftup(最后都是Python代码)。
推荐文章
- 证书验证失败:无法获得本地颁发者证书
- 当使用pip3安装包时,“Python中的ssl模块不可用”
- 无法切换Python与pyenv
- Python if not == vs if !=
- 如何从scikit-learn决策树中提取决策规则?
- 为什么在Mac OS X v10.9 (Mavericks)的终端中apt-get功能不起作用?
- 将旋转的xtick标签与各自的xtick对齐
- 为什么元组可以包含可变项?
- 如何合并字典的字典?
- 如何创建类属性?
- 不区分大小写的“in”
- 在Python中获取迭代器中的元素个数
- 解析日期字符串并更改格式
- 使用try和。Python中的if
- 如何在Python中获得所有直接子目录