파이썬 힙 요소 비교 순서

Question

heapq를 사용하여 우선 순위 큐를 만들기 위해 힙을 사용하고 있습니다.

나는 h 힙 개체입니다

heapq.heappush(h, (cost, node))

, cost가 내 힙을 주문하고 node는 사용자 정의 클래스의 목적하는 항목이다 사용하여 큐에 항목을 삽입합니다. 나는이 코드를 실행하면 내가 SearchNode()이 node

오류의 클래스가 명확하게 것과 동일한 cost

TypeError: unorderable types: SearchNode() < SearchNode()

와 h에 두 개의 서로 다른 항목을 삽입 할 때

, 나는 다음과 같은 오류가 그 파이썬은 두 번째 항목을 비교하고 있습니다.

힙 요소에 대한 비교 순서가 있습니까? 그렇다면 알고리즘에서 두 번째 항목 비교 비교가 시작되지 않도록 어떻게 해결할 수 있습니까? 내 마음에 가능한 한 가지 해결책은 SearchNode() 클래스의 비교 연산자를 오버로드하는 것입니다.

나는 매우 비단뱀에 익숙하다. 그래서 내가 아주 명백한 것을 놓치고 있다면 지적 해주기 바란다. 당신이 현명 노드를 비교하는 방법을 결정할 수있는 경우

class CostAndNode: 
    def __init__(self, cost, node): 
     self.cost = cost 
     self.node = node 

    # do not compare nodes 
    def __lt__(self, other): 
     return self.cost < other.cost 

h = [] 

heapq.heappush(h, CostAndNode(1, node1)) 
heapq.heappush(h, CostAndNode(1, node2)) 

Answer 1

, 당신이 관계를 중단하려면이 옵션을 사용할 수 있습니다

Answer 2

는 비교 노드를 포함하지 않는 작은 클래스를 소개합니다. 예를 들어, 각 노드에는 고유 한 것으로 보장 할 수있는 "레이블"이 할당 될 수 있습니다. 당신은 전적으로 레이블을 비교하여 관계를 깰 수 있습니다. #

class SearchNode: 
    def __init__(self, label): 
     self.label = label 
     #etc 

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

이 (cost, node)의 비교가 결정 있는지 확인합니다.

Answer 3

목록이있는 PQ 및 bisect은 문자열을 예를 들어 저장된 개체로 표시합니다. 저장된 객체의 변경은 필요하지 않습니다. item = (cost, object)을 구성하여 PQ에 삽입하십시오.

import bisect 
# PQ of items 
PQ = [ 
    (10, 'aaa'), 
    (30, 'cccc'), 
    (40, 'dddd'), 
] 

def pq_insert(pq, item): 
    keys = [e[0] for e in pq] 
    i = bisect.bisect(keys, item[0]) 
    pq.insert(i, item) 

e = (20, 'bbbb') 
pq_insert(PQ, e) 

일부 REPL 출력 튜플

>>> print PQ 
[(10, 'aaa'), (30, 'cccc'), (40, 'dddd')] 
>>> e = (20, 'bbbb') 
>>> pq_insert(PQ, e) 
>>> print PQ 
[(10, 'aaa'), (20, 'bbbb'), (30, 'cccc'), (40, 'dddd')] 
>>>