Python包含了用于min-堆的heapq模块，但我需要一个max堆。在Python中我应该使用什么来实现最大堆?
当前回答
python中有内置堆，但我只是想分享一下，如果有人像我一样想自己构建它。 我是python的新手，不要判断我是否犯了错误。 算法是有效的，但效率我不知道
class Heap :
def __init__(self):
self.heap = []
self.size = 0
def add(self, heap):
self.heap = heap
self.size = len(self.heap)
def heappush(self, value):
self.heap.append(value)
self.size += 1
def heapify(self, heap ,index=0):
mid = int(self.size /2)
"""
if you want to travel great value from bottom to the top you need to repeat swaping by the hight of the tree
I don't how how can i get the height of the tree that's why i use sezi/2
you can find height by this formula
2^(x) = size+1 why 2^x because tree is growing exponentially
xln(2) = ln(size+1)
x = ln(size+1)/ln(2)
"""
for i in range(mid):
self.createTee(heap ,index)
return heap
def createTee(self, heap ,shiftindex):
"""
"""
"""
this pos reffer to the index of the parent only parent with children
(1)
(2) (3) here the size of list is 7/2 = 3
(4) (5) (6) (7) the number of parent is 3 but we use {2,1,0} in while loop
that why a put pos -1
"""
pos = int(self.size /2 ) -1
"""
this if you wanna sort this heap list we should swap max value in the root of the tree with the last
value in the list and if you wanna repeat this until sort all list you will need to prevent the func from
change what we already sorted I should decrease the size of the list that will heapify on it
"""
newsize = self.size - shiftindex
while pos >= 0 :
left_child = pos * 2 + 1
right_child = pos * 2 + 2
# this mean that left child is exist
if left_child < newsize:
if right_child < newsize:
# if the right child exit we wanna check if left child > rightchild
# if right child doesn't exist we can check that we will get error out of range
if heap[pos] < heap[left_child] and heap[left_child] > heap[right_child] :
heap[left_child] , heap[pos] = heap[pos], heap[left_child]
# here if the righ child doesn't exist
else:
if heap[pos] < heap[left_child] :
heap[left_child] , heap[pos] = heap[pos], heap[left_child]
# if the right child exist
if right_child < newsize :
if heap[pos] < heap[right_child] :
heap[right_child], heap[pos] = heap[pos], heap[right_child]
pos -= 1
return heap
def sort(self ):
k = 1
for i in range(self.size -1 ,0 ,-1):
"""
because this is max heap we swap root with last element in the list
"""
self.heap [0] , self.heap[i] = self.heap[i], self.heap[0]
self.heapify(self.heap ,k)
k+=1
return self.heap
h = Heap()
h.add([5,7,0,8,9,10,20,30,50,-1] )
h.heappush(-2)
print(" before heapify ")
print(h.heap)
print(" after heapify ")
print(h.heapify(h.heap,0))
print(" after sort ")
print(h.sort())
输出:
之前heapify [5,7,0,8,9,10,20,30,50， -1， -2]
heapify后 [50, 30, 20, 8, 9, 10, 0, 7, 5， -1， -2]
排序后 [-2， -1, 0,5,7,8,9,10,20,30,50]
希望您能理解我的代码。如果有什么你不明白的地方，请发表评论，我会尽力帮助你
其他回答
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))
试试这个
我还需要使用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()调用。
python中有内置堆，但我只是想分享一下，如果有人像我一样想自己构建它。 我是python的新手，不要判断我是否犯了错误。 算法是有效的，但效率我不知道
class Heap :
def __init__(self):
self.heap = []
self.size = 0
def add(self, heap):
self.heap = heap
self.size = len(self.heap)
def heappush(self, value):
self.heap.append(value)
self.size += 1
def heapify(self, heap ,index=0):
mid = int(self.size /2)
"""
if you want to travel great value from bottom to the top you need to repeat swaping by the hight of the tree
I don't how how can i get the height of the tree that's why i use sezi/2
you can find height by this formula
2^(x) = size+1 why 2^x because tree is growing exponentially
xln(2) = ln(size+1)
x = ln(size+1)/ln(2)
"""
for i in range(mid):
self.createTee(heap ,index)
return heap
def createTee(self, heap ,shiftindex):
"""
"""
"""
this pos reffer to the index of the parent only parent with children
(1)
(2) (3) here the size of list is 7/2 = 3
(4) (5) (6) (7) the number of parent is 3 but we use {2,1,0} in while loop
that why a put pos -1
"""
pos = int(self.size /2 ) -1
"""
this if you wanna sort this heap list we should swap max value in the root of the tree with the last
value in the list and if you wanna repeat this until sort all list you will need to prevent the func from
change what we already sorted I should decrease the size of the list that will heapify on it
"""
newsize = self.size - shiftindex
while pos >= 0 :
left_child = pos * 2 + 1
right_child = pos * 2 + 2
# this mean that left child is exist
if left_child < newsize:
if right_child < newsize:
# if the right child exit we wanna check if left child > rightchild
# if right child doesn't exist we can check that we will get error out of range
if heap[pos] < heap[left_child] and heap[left_child] > heap[right_child] :
heap[left_child] , heap[pos] = heap[pos], heap[left_child]
# here if the righ child doesn't exist
else:
if heap[pos] < heap[left_child] :
heap[left_child] , heap[pos] = heap[pos], heap[left_child]
# if the right child exist
if right_child < newsize :
if heap[pos] < heap[right_child] :
heap[right_child], heap[pos] = heap[pos], heap[right_child]
pos -= 1
return heap
def sort(self ):
k = 1
for i in range(self.size -1 ,0 ,-1):
"""
because this is max heap we swap root with last element in the list
"""
self.heap [0] , self.heap[i] = self.heap[i], self.heap[0]
self.heapify(self.heap ,k)
k+=1
return self.heap
h = Heap()
h.add([5,7,0,8,9,10,20,30,50,-1] )
h.heappush(-2)
print(" before heapify ")
print(h.heap)
print(" after heapify ")
print(h.heapify(h.heap,0))
print(" after sort ")
print(h.sort())
输出:
之前heapify [5,7,0,8,9,10,20,30,50， -1， -2]
heapify后 [50, 30, 20, 8, 9, 10, 0, 7, 5， -1， -2]
排序后 [-2， -1, 0,5,7,8,9,10,20,30,50]
希望您能理解我的代码。如果有什么你不明白的地方，请发表评论，我会尽力帮助你
我创建了一个名为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)
最好的方法:
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
推荐文章
- 为什么我得到“'str'对象没有属性'读取'”当尝试使用' json。载入字符串?
- 不区分大小写的列表排序，没有降低结果?
- 排序后的语法(key=lambda:…)
- 在烧瓶中返回HTTP状态代码201
- 使用python创建一个简单的XML文件
- APT命令行界面式的yes/no输入?
- 如何打印出状态栏和百分比?
- 在Python中获取大文件的MD5哈希值
- 在Python格式字符串中%s是什么意思?
- 如何循环通过所有但最后一项的列表?
- 如何有效地清除std::queue ?
- python用什么方法避免默认参数为空列表?
- ValueError: numpy。Ndarray大小改变，可能表示二进制不兼容。期望从C头得到88，从PyObject得到80
- Anaconda /conda -安装特定的软件包版本
- 我在哪里调用Keras的BatchNormalization函数?
