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]
希望您能理解我的代码。如果有什么你不明白的地方，请发表评论，我会尽力帮助你
其他回答
为了详细说明https://stackoverflow.com/a/59311063/1328979，这里有一个针对一般情况的完整文档、注释和测试的Python 3实现。
from __future__ import annotations # To allow "MinHeap.push -> MinHeap:"
from typing import Generic, List, Optional, TypeVar
from heapq import heapify, heappop, heappush, heapreplace
T = TypeVar('T')
class MinHeap(Generic[T]):
'''
MinHeap provides a nicer API around heapq's functionality.
As it is a minimum heap, the first element of the heap is always the
smallest.
>>> h = MinHeap([3, 1, 4, 2])
>>> h[0]
1
>>> h.peek()
1
>>> h.push(5) # N.B.: the array isn't always fully sorted.
[1, 2, 4, 3, 5]
>>> h.pop()
1
>>> h.pop()
2
>>> h.pop()
3
>>> h.push(3).push(2)
[2, 3, 4, 5]
>>> h.replace(1)
2
>>> h
[1, 3, 4, 5]
'''
def __init__(self, array: Optional[List[T]] = None):
if array is None:
array = []
heapify(array)
self.h = array
def push(self, x: T) -> MinHeap:
heappush(self.h, x)
return self # To allow chaining operations.
def peek(self) -> T:
return self.h[0]
def pop(self) -> T:
return heappop(self.h)
def replace(self, x: T) -> T:
return heapreplace(self.h, x)
def __getitem__(self, i) -> T:
return self.h[i]
def __len__(self) -> int:
return len(self.h)
def __str__(self) -> str:
return str(self.h)
def __repr__(self) -> str:
return str(self.h)
class Reverse(Generic[T]):
'''
Wrap around the provided object, reversing the comparison operators.
>>> 1 < 2
True
>>> Reverse(1) < Reverse(2)
False
>>> Reverse(2) < Reverse(1)
True
>>> Reverse(1) <= Reverse(2)
False
>>> Reverse(2) <= Reverse(1)
True
>>> Reverse(2) <= Reverse(2)
True
>>> Reverse(1) == Reverse(1)
True
>>> Reverse(2) > Reverse(1)
False
>>> Reverse(1) > Reverse(2)
True
>>> Reverse(2) >= Reverse(1)
False
>>> Reverse(1) >= Reverse(2)
True
>>> Reverse(1)
1
'''
def __init__(self, x: T) -> None:
self.x = x
def __lt__(self, other: Reverse) -> bool:
return other.x.__lt__(self.x)
def __le__(self, other: Reverse) -> bool:
return other.x.__le__(self.x)
def __eq__(self, other) -> bool:
return self.x == other.x
def __ne__(self, other: Reverse) -> bool:
return other.x.__ne__(self.x)
def __ge__(self, other: Reverse) -> bool:
return other.x.__ge__(self.x)
def __gt__(self, other: Reverse) -> bool:
return other.x.__gt__(self.x)
def __str__(self):
return str(self.x)
def __repr__(self):
return str(self.x)
class MaxHeap(MinHeap):
'''
MaxHeap provides an implement of a maximum-heap, as heapq does not provide
it. As it is a maximum heap, the first element of the heap is always the
largest. It achieves this by wrapping around elements with Reverse,
which reverses the comparison operations used by heapq.
>>> h = MaxHeap([3, 1, 4, 2])
>>> h[0]
4
>>> h.peek()
4
>>> h.push(5) # N.B.: the array isn't always fully sorted.
[5, 4, 3, 1, 2]
>>> h.pop()
5
>>> h.pop()
4
>>> h.pop()
3
>>> h.pop()
2
>>> h.push(3).push(2).push(4)
[4, 3, 2, 1]
>>> h.replace(1)
4
>>> h
[3, 1, 2, 1]
'''
def __init__(self, array: Optional[List[T]] = None):
if array is not None:
array = [Reverse(x) for x in array] # Wrap with Reverse.
super().__init__(array)
def push(self, x: T) -> MaxHeap:
super().push(Reverse(x))
return self
def peek(self) -> T:
return super().peek().x
def pop(self) -> T:
return super().pop().x
def replace(self, x: T) -> T:
return super().replace(Reverse(x)).x
if __name__ == '__main__':
import doctest
doctest.testmod()
https://gist.github.com/marccarre/577a55850998da02af3d4b7b98152cf4
我创建了一个堆包装器，它将值颠倒以创建max-heap，还为min-heap创建了一个包装器类，以使库更像oop。这是要点。有三个班级;Heap(抽象类)，HeapMin和HeapMax。
方法:
isempty() -> bool; obvious
getroot() -> int; returns min/max
push() -> None; equivalent to heapq.heappush
pop() -> int; equivalent to heapq.heappop
view_min()/view_max() -> int; alias for getroot()
pushpop() -> int; equivalent to heapq.pushpop
我还需要使用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()调用。
最简单的方法是反转键的值并使用heapq。例如，将1000.0转换为-1000.0，将5.0转换为-5.0。
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]
希望您能理解我的代码。如果有什么你不明白的地方，请发表评论，我会尽力帮助你
