[PYTHON] 커스텀 비교 술어를 가진 heapq

커스텀 비교 술어를 가진 heapq

사용자 지정 정렬 조건자를 사용하여 힙을 작성하려고합니다. 값이 '사용자 정의'유형이기 때문에 내장 된 비교 술어를 수정할 수 없습니다.

다음과 같은 일을 할 수있는 방법이 있습니까?

h = heapq.heapify([...], key=my_lt_pred)
h = heapq.heappush(h, key=my_lt_pred)

또는 더 나은, 난 내 자신의 컨테이너에 heapq 함수를 래핑 할 수 있으므로 술어를 계속 전달할 필요가 없습니다.

해결법

1. ==============================

   1.heap 문서에 따르면 힙 순서를 사용자 정의하는 방법은 힙의 각 요소를 튜플로 만들고 첫 번째 튜플 요소는 일반적인 파이썬 비교를 허용하는 것입니다.

   heap 문서에 따르면 힙 순서를 사용자 정의하는 방법은 힙의 각 요소를 튜플로 만들고 첫 번째 튜플 요소는 일반적인 파이썬 비교를 허용하는 것입니다.

   heapq 모듈의 함수는 약간 성가기 때문에 (객체 지향적이 아니기 때문에) 항상 힙 객체 (heapified list)가 첫 번째 매개 변수로 명시 적으로 전달되어야합니다. 우리는 하나의 돌로 두 개의 새를 죽일 수 있습니다. 아주 간단한 래퍼 클래스를 만들어서 키 함수를 지정하고 힙을 객체로 제시 할 수 있습니다.

   아래 클래스는 내부 목록을 유지합니다. 각 요소는 터플입니다. 첫 번째 멤버는 키이고, 키 매개 변수를 사용하여 요소 삽입 시간에 계산되며 힙 인스턴스 생성에서 전달됩니다.

   # -*- coding: utf-8 -*-
   import heapq
   
   class MyHeap(object):
      def __init__(self, initial=None, key=lambda x:x):
          self.key = key
          if initial:
              self._data = [(key(item), item) for item in initial]
              heapq.heapify(self._data)
          else:
              self._data = []
   
      def push(self, item):
          heapq.heappush(self._data, (self.key(item), item))
   
      def pop(self):
          return heapq.heappop(self._data)[1]
   

2. ==============================

   2.heap 문서는 힙 요소가 첫 번째 요소가 우선 순위이고 정렬 순서를 정의하는 튜플이라고 제안합니다.

   heap 문서는 힙 요소가 첫 번째 요소가 우선 순위이고 정렬 순서를 정의하는 튜플이라고 제안합니다.

   그러나 당신의 질문과 더 관련이있다. 문서에는 정렬 안정성과 다른 우선 순위가있는 요소의 문제를 처리하기 위해 자신의 heapq 래퍼 함수를 ​​어떻게 구현할 수 있는지에 대한 샘플 코드가 담긴 토론이 포함되어있다.

   요컨대, 그들의 해결책은 heapq의 각 요소를 우선 순위, 항목 수 및 삽입 할 요소가있는 트리플로 만드는 것입니다. 항목 수는 힙에 추가 된 순서대로 정렬 된 우선 순위가 동일한 요소를 보장합니다.

3. ==============================

   3.두 대답의 한계는 동점이 동점으로 취급되는 것을 허용하지 않는다는 것입니다. 첫 번째 항목은 입력 항목을 비교하여 두 번째 항목에서 항목을 비교하여 연결이 끊어집니다. 동점이 동점이되도록하는 것이 더 빠르며, 그들 중 많은 것이 있으면 큰 차이를 만들 수 있습니다. 위 및 문서를 기반으로, 이것이 heapq에서 달성 될 수 있는지는 명확하지 않습니다. heapq가 키를 허용하지 않는 것은 이상한 것처럼 보이지만 동일한 모듈에서 키를 가져 오는 기능은 그렇습니다. 추신.: 첫 번째 주석 ( "duplicate ...")의 링크를 따라 가면 해결책을 제시하는 le 정의에 대한 또 다른 제안이 있습니다.

   두 대답의 한계는 동점이 동점으로 취급되는 것을 허용하지 않는다는 것입니다. 첫 번째 항목은 입력 항목을 비교하여 두 번째 항목에서 항목을 비교하여 연결이 끊어집니다. 동점이 동점이되도록하는 것이 더 빠르며, 그들 중 많은 것이 있으면 큰 차이를 만들 수 있습니다. 위 및 문서를 기반으로, 이것이 heapq에서 달성 될 수 있는지는 명확하지 않습니다. heapq가 키를 허용하지 않는 것은 이상한 것처럼 보이지만 동일한 모듈에서 키를 가져 오는 기능은 그렇습니다. 추신.: 첫 번째 주석 ( "duplicate ...")의 링크를 따라 가면 해결책을 제시하는 le 정의에 대한 또 다른 제안이 있습니다.

from https://stackoverflow.com/questions/8875706/heapq-with-custom-compare-predicate by cc-by-sa and MIT license