Python包含了用于min-堆的heapq模块,但我需要一个max堆。在Python中我应该使用什么来实现最大堆?
当前回答
如果插入的键具有可比性但不像int型,则可能重写它们上的比较操作符(即<=变成>,>变成<=)。否则,您可以重写heapq。heapq模块中的_siftup(最后都是Python代码)。
其他回答
如果插入的键具有可比性但不像int型,则可能重写它们上的比较操作符(即<=变成>,>变成<=)。否则,您可以重写heapq。heapq模块中的_siftup(最后都是Python代码)。
你可以使用
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
最好的方法:
from heapq import *
h = [5, 7, 9, 1, 3]
h_neg = [-i for i in h]
heapify(h_neg) # heapify
heappush(h_neg, -2) # push
print(-heappop(h_neg)) # pop
# 9
允许您选择任意数量的最大或最小的项目
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]
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))
试试这个
推荐文章
- 证书验证失败:无法获得本地颁发者证书
- 当使用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中获得所有直接子目录