파이썬에는 최소 힙에 대한 heapq 모듈이 포함되어 있지만 최대 힙이 필요합니다. 파이썬에서 max-heap 구현을 위해 무엇을 사용해야합니까?
답변
가장 쉬운 방법은 키 값을 반전시키고 heapq를 사용하는 것입니다. 예를 들어 1000.0을 -1000.0으로, 5.0을 -5.0으로 바꿉니다.
답변
당신이 사용할 수있는
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답변
해결책은 값을 힙에 저장할 때 값을 부정하거나 다음과 같이 객체 비교를 반전시키는 것입니다.
import heapq
class MaxHeapObj(object):
def __init__(self, val): self.val = val
def __lt__(self, other): return self.val > other.val
def __eq__(self, other): return self.val == other.val
def __str__(self): return str(self.val)최대 힙의 예 :
maxh = []
heapq.heappush(maxh, MaxHeapObj(x))
x = maxh[0].val # fetch max value
x = heapq.heappop(maxh).val # pop max value그러나 값을 줄 바꿈 및 줄 바꿈을 기억해야합니다. 최소 / 최대 힙을 다룰 때 알아야합니다.
MinHeap, MaxHeap 클래스
클래스 MinHeap와 MaxHeap객체를 추가하면 코드를 단순화 할 수 있습니다.
class MinHeap(object):
def __init__(self): self.h = []
def heappush(self, x): heapq.heappush(self.h, x)
def heappop(self): return heapq.heappop(self.h)
def __getitem__(self, i): return self.h[i]
def __len__(self): return len(self.h)
class MaxHeap(MinHeap):
def heappush(self, x): heapq.heappush(self.h, MaxHeapObj(x))
def heappop(self): return heapq.heappop(self.h).val
def __getitem__(self, i): return self.h[i].val사용법 예 :
minh = MinHeap()
maxh = MaxHeap()
# add some values
minh.heappush(12)
maxh.heappush(12)
minh.heappush(4)
maxh.heappush(4)
# fetch "top" values
print(minh[0], maxh[0]) # "4 12"
# fetch and remove "top" values
print(minh.heappop(), maxh.heappop()) # "4 12"답변
가장 쉽고 이상적인 솔루션
값에 -1을 곱하십시오
당신은 간다. 가장 높은 숫자는 모두 가장 낮으며 그 반대도 마찬가지입니다.
요소를 팝 할 때 원래 값을 다시 얻기 위해 -1을 곱하는 요소를 기억하십시오.
답변
heapq의 최대 힙 버전을 구현하고 PyPI에 제출했습니다. (heapq 모듈 CPython 코드가 약간 변경되었습니다.)
https://pypi.python.org/pypi/heapq_max/
https://github.com/he-zhe/heapq_max
설치
pip install heapq_max용법
tl; dr : 모든 함수에 ‘_max’를 추가하는 것을 제외하고 heapq 모듈과 동일합니다.
heap_max = [] # creates an empty heap
heappush_max(heap_max, item) # pushes a new item on the heap
item = heappop_max(heap_max) # pops the largest item from the heap
item = heap_max[0] # largest item on the heap without popping it
heapify_max(x) # transforms list into a heap, in-place, in linear time
item = heapreplace_max(heap_max, item) # pops and returns largest item, and
# adds new item; the heap size is unchanged답변
비교 가능하지만 int와는 다른 키를 삽입하는 경우 비교 연산자를 대체 할 수 있습니다 (예 : <=가> 및>가 <=가 됨). 그렇지 않으면 heapq 모듈에서 heapq._siftup을 재정의 할 수 있습니다 (결국 파이썬 코드 일뿐입니다).
답변
임의의 양의 최대 또는 최소 항목을 선택할 수 있도록 허용
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]