Python에서 max-heap을 구현하려면 무엇을 사용해야 합니까?

Python에서 max-heap을 구현하려면 무엇을 사용해야 합니까?

파이썬에는 최소 힙을 위한 힙큐 모듈이 포함되어 있지만 최대 힙이 필요합니다.Python에서 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)

max-heap의 예:

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을 곱하면 원래 값을 다시 얻을 수 있습니다.

가장 쉬운 방법은 모든 요소를 음으로 변환하는 것입니다. 그러면 문제가 해결됩니다.

import heapq
heap = []
heapq.heappush(heap, 1*(-1))
heapq.heappush(heap, 10*(-1))
heapq.heappush(heap, 20*(-1))
print(heap)

출력은 다음과 같습니다.

[-20, -1, -10]

히프q의 최대 히프 버전을 구현하여 PyPI에 제출하였습니다.(히프q 모듈 CPython 코드의 매우 작은 변경)

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

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

인스톨

pip install heapq_max

사용.

tl;dr: 모든 함수에 '_max'를 추가하는 것을 제외하고 힙큐 모듈과 동일합니다.

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

것입니다.MaxHeap「」에 한 실장heapq하지만.. 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아.

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음음음같 뭇매하다

import heapq


def heappush(heap, item):
    return heapq.heappush(heap, -item)


def heappop(heap):
    return -heapq.heappop(heap)

내 ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★.heapq.heappush() ★★★★★★★★★★★★★★★★★」heapq.heappop()" " 를 한 콜heappush() ★★★★★★★★★★★★★★★★★」heappop()각각 다음과 같다.

유사하지만 int와 유사하지 않은 키를 삽입할 경우 해당 키의 비교 연산자를 덮어쓸 수 있습니다(예: <=가 되고 >가 <=가 됩니다).그렇지 않으면 heapq를 덮어쓸 수 있습니다.heapq 모듈의 _siftup(결국 모두 Python 코드일 뿐입니다).

int 클래스를 확장하고 __lt__를 덮어쓰는 것도 방법 중 하나입니다.

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()

최적의 방법:

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

최대 항목 또는 최소 항목 중 임의의 양을 선택할 수 있습니다.

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]

값을 반전시켜 max-heap을 작성하는 힙 래퍼와 라이브러리를 OOP처럼 만들기 위한 min-heap 래퍼 클래스를 만들었습니다.요점은 이렇다.Heap(추상 클래스), HeapMin 및 HeapMax의 3가지 클래스가 있습니다.

방법:

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

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

heapq 모듈에는 maxheap을 구현하기 위해 필요한 모든 것이 있습니다.max-heap의 히푸시 기능만 수행합니다.아래에서 이를 극복하는 방법을 시연했습니다. ⬇

heapq 모듈에 다음 함수를 추가합니다.

def _heappush_max(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown_max(heap, 0, len(heap)-1)

그리고 마지막에 다음을 추가합니다.

try:
    from _heapq import _heappush_max
except ImportError:
    pass

됐어! 됐어!

PS - heapq 함수로 이동하려면 먼저 편집기에 "import heapq"라고 쓴 다음 "heapq"를 오른쪽 클릭하고 "definition"으로 이동합니다.

최대 힙을 사용하여 가장 큰 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에 built in hump이 있지만, 나처럼 직접 만들고 싶은 사람이 있다면 이것을 공유하고 싶다. 나는 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())

출력:

히피화 전 [5, 7, 0, 8, 9, 10, 20, 30, 50, -1, -2]

힙화 후 [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))

이거 먹어봐

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