파이썬에서 max-heap 구현에 무엇을 사용합니까?

파이썬에서 max-heap 구현에 무엇을 사용합니까?

---

파이썬에는 최소 힙에 대한 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,MaxHeapInt(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을 곱하십시오

There you go. All the highest numbers are now the lowest and vice versa.

Just remember that when you pop an element to multiply it with -1 in order to get the original value again.

---

If you are inserting keys that are comparable but not int-like, you could potentially override the comparison operators on them (i.e. <= become > and > becomes <=). Otherwise, you can override heapq._siftup in the heapq module (it's all just Python code, in the end).

---

Allowing you to chose an arbitrary amount of largest or smallest items

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]

---

I implemented a max heap version of heapq and submitted it to PyPI. (Very slight change of heapq module CPython code.)

https://pypi.python.org/pypi/heapq_max/

https://github.com/he-zhe/heapq_max

Installation

pip install heapq_max

Usage

tl;dr: same as heapq module except adding ‘_max’ to all functions.

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

---

Extending the int class and overriding __lt__ is one of the ways.

import queue
class MyInt(int):
    def __lt__(self, other):
        return self > other

def main():
    q = queue.PriorityQueue()
    q.put(MyInt(10))
    q.put(MyInt(5))
    q.put(MyInt(1))
    while not q.empty():
        print (q.get())


if __name__ == "__main__":
    main()

---

I have created a heap wrapper that inverts the values to create a max-heap, as well as a wrapper class for a min-heap to make the library more OOP-like. Here is the gist. There are three classes; Heap (abstract class), HeapMin, and HeapMax.

Methods:

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

참고URL : https://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python