고정 크기 힙 파이썬 유지

고정 크기 힙 파이썬 유지

h = []
heapq.heappush(h,(10, 1200))
heapq.heappush(h,(20, 31))
heapq.heappush(h,(5, 1))

나는 say 3의 고정 힙 크기를 유지하고 싶기 때문에, 내가 다음에 가질 때, 값 20을 가진 키는 삭제되고 나는 값 3, 5, 10을 남긴다.어떻게 하는지 알아?

---

크기를 확인할 수 있는 hipq에 내장된 것이 없기 때문에 직접 확인해야 합니다:

if len(h) < capacity:
    heapq.heappush(h, thing)
else:
    # Equivalent to a push, then a pop, but faster
    spilled_value = heapq.heappushpop(h, thing)
    do_whatever_with(spilled_value)

또한 hipq는 최대 힙이 아닌 최소 힙을 구현합니다. 당신은 아마도 우선순위를 부정함으로써 우선순위의 순서를 뒤집어야 할 것이다.

---

고정 크기의 상위 n 힙을 구현하려고 했던 이 게시물을 찾았습니다. 다음은 제가 제공할 수 있는 솔루션입니다:

from heapq import heapify, heappush, heappushpop, nlargest

class MaxHeap():
    def __init__(self, top_n):
        self.h = []
        self.length = top_n
        heapify( self.h)
        
    def add(self, element):
        if len(self.h) < self.length:
            heappush(self.h, element)
        else:
            heappushpop(self.h, element)
            
    def getTop(self):
        return sorted(self.h, reverse=True)

그리고 더 최적 (@CyanoKobalamine 덕분에)

from heapq import heapify, heappush, heappushpop, nlargest

class MaxHeap():
    def __init__(self, top_n):
        self.h = []
        self.length = top_n
        heapify( self.h)
        
    def add(self, element):
        if len(self.h) < self.length:
            heappush(self.h, element)
        else:
            heappushpop(self.h, element)
            
    def getTop(self):
        return nlargest(self.length, self.h)

---

모든 푸시에서 고정 크기 최소 힙의 가장 큰 요소를 폐기하는 것과 같은 가장 작은 요소를 원하는 경우 힙을 구성할 대상에서 사용(또는 반대로 사용)해야 합니다.

---

Python(오늘날 v 3.8x)에는 고정 힙 크기 기능이 내장되어 있지 않습니다. 넌 두가지 옵션이 있다 :

1. 더미를 유지하고 모든 푸시를 할 때마다 터뜨리는지 확인하십시오. 이는 주어진 시간에 힙의 최대 크기가 하나를 터뜨릴 때라는 것을 의미한다.

2. 다른 옵션은 다음과 같이 사용하는 것입니다:

힙에서 가장 작은 항목을 팝업하여 반환하고 새 항목도 푸시합니다. 힙 크기는 변경되지 않습니다. 힙이 비어 있으면 IndexError가 발생합니다. 이 한 단계 작업은 heappop() 다음에 heappush()를 수행하는 것보다 더 효율적이며 를 사용할 때 더 적합할 수 있습니다.

---

나는 최대 길이의 정렬된 항목 목록인 이런 것이 나 자신에게 필요했다.

나는 그것의 'maxlen' 속성 때문에 dque를 사용했다.

import collections
import bisect

h = collections.deque(maxlen=3)

def insert(h, item):
    if len(h) < h.maxlen or item < h[-1]:
        if len(h) == h.maxlen:
            h.pop()
        bisect.insort_left(h, item)

>>> insert(h, 200); print(h)
deque([200], maxlen=3)

>>> insert(h, 100); print(h)
deque([100, 200], maxlen=3)

>>> insert(h, 200); print(h)
deque([100, 200, 200], maxlen=3)

>>> insert(h, 150); print(h)
deque([100, 150, 200], maxlen=3)

>>> insert(h, 200); print(h)
deque([100, 150, 200], maxlen=3)

>>> insert(h, 1); print(h)
deque([1, 100, 150], maxlen=3)

>>> insert(h, 100); print(h)
deque([1, 100, 100], maxlen=3)

>>> insert(h, 20); print(h)
deque([1, 20, 100], maxlen=3)

---

제한된 크기의 힙을 얻기 위해 모든 푸시 작업 후 힙을 잘라낼 수 있습니다.

limited_sized_heap = limited_sized_heap[:max_size_of_heap]

여기 예시가 있다.

import random
import heapq

max_size_of_heap = 5
limited_sized_heap = []    

for i in range(10):
   a_random = random.randint(1,9)
   heapq.heappush( limited_sized_heap, a_random )
   limited_sized_heap = limited_sized_heap[:max_size_of_heap]
   print(limited_sized_heap)

출력:

[3]
[3, 9]
[3, 9, 4]
[3, 4, 4, 9]
[2, 3, 4, 9, 4]
[1, 3, 2, 9, 4]
[1, 3, 1, 9, 4]
[1, 3, 1, 9, 4]
[1, 3, 1, 9, 4]
[1, 3, 1, 9, 4]

제한된 크기 대신 절대 고정 크기의 힙이 필요한 경우 무한대의 고정 크기 목록으로 힙을 초기화하면 됩니다.

fixed_sized_heap = [float('inf')] * heap_size

---

크기를 확인할 수 있는 hipq 기능이 내장되어 있지 않으므로 직접 확인해야 합니다:

if len(h) < capacity:
    heapq.heappush(h, thing)
else:
    # pushes the element on and then pops off the top
    heapq.heappushpop(h, thing)

hipq는 최대 힙이 아닌 최소 힙을 구현합니다. 우선순위의 순서를 되돌려야 합니다

나는 당신이 게시물에서 고정 크기가 3인 최대 힙을 원하고, 새로운 힙을 추가할 때 최소 요소를 유지할 수 있다고 구체적으로 언급한 것을 보았다

최소 힙에 삽입할 때 요소를 비활성화하면 힙푸시 팝을 사용할 수 있습니다. 가장 작은 요소를 제거하고 교체하는 대신 이제 가장 큰 요소를 제거하고 교체해야 합니다

이렇게 하면 요소를 꺼낼 때 크기의 역순으로 볼 수 있다는 단점이 있습니다. 따라서 모든 것의 끝에 올바르게 정렬된 오름차순 목록을 원한다면 그들을 무효화하고 그들의 순서를 뒤집어야 할 것이다

다음은 예시입니다:

기본 Minheep을 사용할 때와 Minheep의 요소를 비활성화할 때의 푸시 팝 시각화

게시물에 설명된 것과 동일한 요구 사항으로 특정 문제에서 구현되는 방법의 예가 있습니다