Python의 사용자 정의 데이터 유형이있는 최소 힙 (heap)?

Question

파이썬에서 Inpainting을위한 Fast Marching Method를 구현하고 싶습니다. 문헌에서 이것은 min-heap을 사용하여 구현되었습니다. 데이터 구조를 추가, 제거 및 재정렬하는 작업을 여러 번 수행하고 매번 가장 작은 요소를 추출하기 때문입니다. 따라서 이러한 작업의 복잡성은 최소가되어야합니다.

파이썬에는 heapq 내장 모듈이 있다는 것을 알고 있습니다. 단일 float 값을 허용합니다. 그러나 픽셀에 해당하는 3 가지 정보 내용을 저장해야합니다. 목록을 수락하려면 heapq을 조정할 수있는 방법이 있습니까?

또는이 기능이있는 다른 데이터 구조가 있습니까?

Answer 1

heapq은 주문할 수있는 한 유형을 취합니다. 이 있습니다. 항목은 <보다 작거나 <=보다 작거나 같아야합니다 (heapq은 첫 번째 값을 사용할 수없는 경우 후자를 사용합니다).

예를 들어 튜플 ((priority, your_data_structure))을 사용할 수 있습니다. 튜플은 첫 번째 항목부터 해당 내용을 기준으로 상대적인 순서를 갖습니다.

또는 당신이 순서를 정의하여 그들 사이의 비교를 구현하기 위해 적어도 __lt__ 중 하나 __le__, __gt__ 또는 __ge__를 구현하는 사용자 정의 개체를 사용할 수 있습니다 (바람직하고, 너무 __eq__ 평등 방법을 포함). functools. total_ordering() decorator는 나머지 방법으로 클래스를 제공합니다 :

from functools import total_ordering 

@total_ordering 
class PixelInfo(object): 
    def __init__(self, r, g, b): 
     self.r, self.g, self.b = r, g, b 

    def __eq__(self, other): 
     if not isinstance(other, type(self)): return NotImplemented 
     return all(getattr(self, c) == getattr(other, c) for c in 'rgb') 

    def __lt__(self, other): 
     if not isinstance(other, type(self)): return NotImplemented 
     return self.r + self.g + self.b < other.r + other.g + other.b 

당신을 위해 처리하게 행복 할 heapq 주문 가능한 사용자 정의 클래스가 될 것입니다.