python - Pythonの最小ヒープ

Question

カスタム比較関数を定義して、オブジェクトのセットを最小ヒープに格納したいと思います。Pythonディストリビューションの一部として利用可能なheapqモジュールがあるようです。このモジュールでカスタムコンパレータを使用する方法はありますか？そうでない場合は、他の誰かがカスタムの最小ヒープを構築しましたか？

Answer 1

2つのオプション（Devin Jeanpierreの提案は別として）：

1. ヒープを使用する前にデータを装飾します。これは、key=ソートのオプションに相当します。たとえば、(何らかの理由で) サインに従って数値のリストをヒープ化したい場合:

   data = [ # list of numbers ]
   heap = [(math.sin(x), x) for x in data]
   heapq.heapify(heap)
   # get the min element
   item = heappop(heap)[1]
   

2. heapqモジュールは純粋な python で実装されています。それを作業ディレクトリにコピーして、関連するビットを変更するだけです。簡単に見ると、siftdown() と siftup() を変更する必要があり、必要に応じて nlargest と nsmallest を変更する必要があります。

Answer 2

はい、方法があります。カスタムコンパレータを実装するラッピングクラスを定義し、実際のオブジェクトのリストの代わりにそれらのリストを使用します。これは、ソート関数/メソッドのようにkey=またはcmp=引数を提供しないため、heapqモジュールを使用しているときの最良の方法です。

def gen_wrapper(cmp):
    class Wrapper(object):
        def __init__(self, value): self.value = value
        def __cmp__(self, obj): return cmp(self.value, obj.value)
    return Wrapper