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))
试试这个
其他回答
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))
试试这个
最简单最理想的解决方案
将这些值乘以-1
好了。所有最高的数字现在都是最低的,反之亦然。
只要记住,当您弹出一个元素与-1相乘以再次获得原始值时。
这是一个基于heapq的简单MaxHeap实现。虽然它只适用于数值。
import heapq
from typing import List
class MaxHeap:
def __init__(self):
self.data = []
def top(self):
return -self.data[0]
def push(self, val):
heapq.heappush(self.data, -val)
def pop(self):
return -heapq.heappop(self.data)
用法:
max_heap = MaxHeap()
max_heap.push(3)
max_heap.push(5)
max_heap.push(1)
print(max_heap.top()) # 5
我创建了一个名为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)
如果你想用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]
推荐文章
- 如何在Python中进行热编码?
- 如何嵌入HTML到IPython输出?
- 在Python生成器上使用“send”函数的目的是什么?
- 是否可以将已编译的.pyc文件反编译为.py文件?
- Django模型表单对象的自动创建日期
- 在Python中包装长行
- 如何计算两个时间串之间的时间间隔
- 我如何才能找到一个Python函数的参数的数量?
- 您可以使用生成器函数来做什么?
- 将Python诗歌与Docker集成
- 提取和保存视频帧
- 使用请求包时出现SSL InsecurePlatform错误
- 如何检索Pandas数据帧中的列数?
- except:和except的区别:
- 错误:“字典更新序列元素#0的长度为1;2是必需的”