[python] 사용자 정의 비교 술어가있는 heapq

Program / 글쓴이

사용자 지정 정렬 조건 자로 힙을 만들려고합니다. 여기에 들어가는 값은 ‘사용자 정의’유형이므로 내장 된 비교 술어를 수정할 수 없습니다.

다음과 같은 방법이 있습니까?

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

또는 더 좋은 점은 내 컨테이너에 heapq 함수를 래핑하여 술어를 계속 전달할 필요가 없다는 것입니다.

답변

heapq 문서 에 따르면 힙 순서를 사용자 정의하는 방법은 힙의 각 요소가 튜플이되도록하는 것입니다. 첫 번째 튜플 요소는 일반적인 Python 비교를 허용하는 요소입니다.

heapq 모듈의 함수는 약간 번거롭고 (객체 지향적이지 않기 때문에) 항상 첫 번째 매개 변수로 명시 적으로 전달되는 힙 객체 (힙화 된 목록)가 필요합니다. 하나의 돌로 두 마리의 새를 죽일 수 있습니다.key함수 하고 힙을 객체로 .

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

# -*- coding: utf-8 -*-
import heapq

class MyHeap(object):
   def __init__(self, initial=None, key=lambda x:x):
       self.key = key
       self.index = 0
       if initial:
           self._data = [(key(item), i, item) for i, item in enumerate(initial)]
           self.index = len(self._data)
           heapq.heapify(self._data)
       else:
           self._data = []

   def push(self, item):
       heapq.heappush(self._data, (self.key(item), self.index, item))
       self.index += 1

   def pop(self):
       return heapq.heappop(self._data)[2]

(추가 self.index부분은 평가 된 키 값이 그리기이고 저장된 값이 직접 비교할 수 없을 때 충돌을 방지하는 것입니다. 그렇지 않으면 heapq가 TypeError로 실패 할 수 있습니다)

답변

__lt__()함수 를 재정의하는 클래스를 정의 합니다. 아래 예를 참조하십시오 (Python 3.7에서 작동).

import heapq

class Node(object):
    def __init__(self, val: int):
        self.val = val

    def __repr__(self):
        return f'Node value: {self.val}'

    def __lt__(self, other):
        return self.val < other.val

heap = [Node(2), Node(0), Node(1), Node(4), Node(2)]
heapq.heapify(heap)
print(heap)  # output: [Node value: 0, Node value: 2, Node value: 1, Node value: 4, Node value: 2]

heapq.heappop(heap)
print(heap)  # output: [Node value: 1, Node value: 2, Node value: 2, Node value: 4]

답변

heapq 문서는 힙 요소는 첫 번째 요소는 우선 순위 및 정렬 순서를 정의하는 튜플이 될 수 있음을 시사한다.

그러나 귀하의 질문과 더 관련이 있다는 것은 문서에 자체 heapq 래퍼 함수를 ​​구현하여 정렬 안정성 및 동일한 우선 순위를 가진 요소 (다른 문제 중에서) 문제를 처리하는 방법에 대한 샘플 코드 에 대한 토론이 포함되어 있다는 것입니다.

요컨대, 그들의 해결책은 heapq의 각 요소가 우선 순위, 항목 수 및 삽입 할 요소가있는 트리플이되도록하는 것입니다. 항목 수는 같은 우선 순위를 가진 요소가 힙에 추가 된 순서대로 정렬되도록합니다.

답변

두 답변의 한계는 동점이 동점으로 취급되는 것을 허용하지 않는다는 것입니다. 첫 번째는 항목을 비교하여 연결을 끊고 두 번째는 입력 순서를 비교하여 연결합니다. 동점을 묶어 두는 것이 더 빠르며, 많은 경우 큰 차이를 만들 수 있습니다. 위와 문서를 기반으로 이것이 heapq에서 달성 될 수 있는지 명확하지 않습니다. heapq가 키를 받아들이지 않는 반면 동일한 모듈에서 파생 된 함수는 키를 받아들이지 않는 것이 이상해 보입니다.
추신 : 첫 번째 주석 ( “중복 가능성 …”)의 링크를 따라 가면 해결책처럼 보이는 파일을 정의하는 또 다른 제안이 있습니다.

답변

setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)

heapq의 객체 값을 비교할 때 사용합니다.

답변