Pythonはいくつかの属性でheapify、属性の変更後にreheapify

Question

私はpython 3.5標準ライブラリで同じタイプのオブジェクトの優先順位キューを作るためにheapqモジュールを使用しようとしています。私はオブジェクトの属性に基づいてheapifyし、それらの属性のいくつかの値を変更し、新しい値に基づいて再度heapifyすることができるようにしたいと思います。私はこれをやってどうやって行くのだろうかと思っています。

import heappq 
class multiNode: 
    def __init__(self, keyValue): 
     self.__key = keyValue 
    def setKey(self, keyValue): 
     self.__key = keyValue 
    def getKey(self): 
     return self.__key 

queue = [multiNode(1), multiNode(2), multiNode(3)] 
heapq.heapify(queue) #want to heapify by whatever getKey returns for each node 
queue[0].setKey(1000) 
heapq.heapify(queue) #re heapify with those new values 

Answer 1

コードを作成するにはさまざまな方法があります。たとえば、あなたはrich comparison operator methodsの一部を実装することで、あなたのアイテムが注文可能にする（そしておそらく、残りを実装するためにfunctools.total_orderingを使用）できます。

@functools.total_ordering 
class multiNode: 
    def __init__(self, keyValue): 
     self.__key = keyValue 
    def setKey(self, keyValue): 
     self.__key = keyValue 
    def getKey(self): 
     return self.__key 
    def __eq__(self, other): 
     if not isinstance(other, multiNode): 
      return NotImplemented 
     return self.__key == other.__key 
    def __lt__(self, other): 
     if not isinstance(other, multiNode): 
      return NotImplemented 
     return self.__key < other.__key 

これはあなたのコードの作業を行いますが、あなたをreheapifyすることは非常に効率的ではないかもしれませんキュー内にノードを変更するたびに、特にキューに多数のノードがある場合は、キューに格納されます。キューエントリを削除したりヒーププロパティに違反することなくキューエントリを無効にできるように、キューの周りに余分なロジックを書く方が良いでしょう。その後、更新する必要があるアイテムがある場合は、古いエントリを無効にして、新しい優先度の新しいアイテムを追加します。

ディクショナリを使用してノードインスタンスから[pritority, node]リストにマップする、すばやく実装された実装です。ノードの優先度が更新されると、辞書がチェックされ、リストの一部のnodeがNoneに設定されます。無効なエントリは、ノードをキューの前面からポップするときに無視されます。

queue = [] 
queue_register = {} 

def add_to_queue(node) 
    item = [node.getKey(), node] 
    queue.heappush(queue, item) 
    queue_register[node] = item 

def update_key_in_queue(node, new_key): 
    queue_register[node][1] = None # invalidate old item 
    node.setKey(new_key) 
    add_to_queue(node) 

def pop_from_queue(): 
    node = None 
    while node is None: 
     _, node = heapq.heappop(queue) # keep popping items until we find one that's valid 
    del queue_register[node] # clean up our bookkeeping record 
    return node 

これをテストして、プログラムの実際のキューの使用が速いかどうかを確認することができます。 （あなたがあなたの質問にについて尋ねていたものとは無関係な）自分のmultiNodeクラスについて

数最終ノート：

あなたは非常にPython的ではないクラスでやっているものがいくつかあります。まず、Pythonの最も一般的な命名規則では、クラスにはCapitalizedNames、それ以外のすべての変数（すべての種類、関数、モジュールの変数）にはlower_case_names_with_underscoresが使用されています。

__keyの二重先頭アンダースコアを使用する別の問題。二重先頭の（そして末尾ではない）不要コードは、Pythonの名前マングリングシステムを呼び出します。これは、変数をプライベートにする方法として意図されているように思えるかもしれませんが、実際にはそうではありません。プロキシオブジェクト（他のオブジェクトの属性を模倣する）やmixinクラス（未知の属性を持つ他の型に継承されるかもしれない）の属性を設定しているときなど、 ）。クラス外のコードが、multiNodeクラスの変更された属性__keyに実際にアクセスしたい場合は、_multiNode__keyを使用しても変更できます。何かがであることを暗示するために、をプライベート属性とするには、単一のアンダースコア_keyを使用してください。

それで私の最終的な問題は、keyはおそらく私的ではないはずです。 getXとsetXメソッドを使用してプライベートインスタンス変数を変更するのは、非常にPythonicではありません。属性がクラスのパブリックAPIの一部であることを文書化し、他のコードがそのAPIに直接アクセスできるようにすることは、はるかに一般的です。後でアトリビュートが参照または変更されたときに何か面白くする必要があると判断した場合は、property記述子を使用して、属性アクセスをgetterおよびsetter関数の呼び出しに自動的に変換できます。後で属性APIの実装を変更する方法はないため、他のプログラミング言語は通常、パブリック属性ではなくゲッターとセッターで始まります。だからとにかく、あなたのクラスの__init__をself.key = keyValueに設定し、setKeyとgetKeyを完全に取り除くようにしましょう！

Answer 2

あなたが探しているものをやって粗方法はid()方法で構築dictsやPythonのを使用することです。このメソッドは、基本的にヒープをオブジェクトのidのヒープとして保持し、そのオブジェクトをがキーであるdictにアクセスして更新することを許可します。私は私のローカルマシン上でこれを試してみました、あなたが探しているものをやっているようだ：

import heapq 
class multiNode: 
    def __init__(self, keyValue): 
     self.__key = keyValue 
    def setKey(self, keyValue): 
     self.__key = keyValue 
    def getKey(self): 
     return self.__key 

first_node = multiNode(1) 
second_node = multiNode(2) 
thrid_node = multiNode(3) 
# add more nodes here 
q = [id(first_node), id(second_node), id(third_node)] 
mutilNode_dict = { 
    id(first_node): first_node, 
    id(second_node): second_node, 
    id(third_node): third_node 
} 
heapq.heapify(q) 
multiNode_dict[q[0]].setKey(1000) 
heapq.heapify(q) 

heapify()は本当に多く、ここであまりにも行うことはありません、それが削除されるまで、オブジェクトのidが同じであることを行っているので、 。ヒープに新しいオブジェクトを追加してオブジェクトを取り出す場合には、より便利です。