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

Question

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

같은 것을 할 수있는 방법이 있나요 :

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

또는 더 나은, 나는 그래서 나는 술어를 통과 보관할 필요가없는 내 자신의 용기에 heapq 기능을 포장 할 수있다.

Answer 1

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

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

클래스 이하 각 요소 힙 인스턴스에 전달 key 파라미터를 이용하여 소자의 삽입시에 산출 된 키이며, 제 1 부재하는 튜플이다 내부에서, 유지 :

# -*- 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] 

Answer 2

heapq documentation은 힙 요소가 첫 번째 요소가 우선 순위이고 정렬 순서를 정의하는 튜플이 될 수 있음을 제안합니다.

그러나 더 많은 질문과 관련하여 문서에는 정렬 안정성 문제와 동일한 우선 순위 (다른 문제 중에서도) 요소 문제를 처리하기 위해 자신의 heapq 래퍼 함수를 ​​구현하는 방법에 대한 discussion with sample code이 포함되어 있습니다.

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

Answer 3

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