プライオリティキューの優先順位を変更する（効率的な方法）

Question

プライオリティキュー内のアイテムの優先順位を変更する効率的な方法を探しています。私はheapqに基づいて（非常に素朴な）優先度キューインプリメンテーションを持っています。ここ

from heapq import heapify, heappop 

class pq(object): 
    def __init__(self, init= None): 
     self.inner, self.item_f= [], {} 
     if not None is init: 
      self.inner= [[priority, item] for item, priority in enumerate(init)] 
      heapify(self.inner) 
      self.item_f= {pi[1]: pi for pi in self.inner} 

    def top_one(self): 
     if not len(self.inner): return None 
     priority, item= heappop(self.inner) 
     del self.item_f[item] 
     return item, priority 

    def re_prioritize(self, items, prioritizer= lambda x: x+ 1): 
     for item in items: 
      if not item in self.item_f: continue 
      entry= self.item_f[item] 
      entry[0]= prioritizer(entry[0]) 
     heapify(self.inner) 

そして、ちょうど私の実際のアプリケーションに優先順位を変更特性を実証するための簡単なコルーチンです：関連する部分は次のようにしています。テスト

if __name__ == '__main__': 
    def gen_tst(n= 3): 
     priorities= range(n) 
     priorities.reverse() 
     priorities= priorities+ range(n) 
     def tst(): 
      result, f= range(2* n), fecther(priorities) 
      k, item_t= f.next() 
      while not None is item_t: 
       result[k]= item_t[0] 
       k, item_t= f.send(range(item_t[0])) 
      return result 
     return tst 

で

def fecther(priorities, prioritizer= lambda x: x+ 1): 
    q= pq(priorities) 
    for k in xrange(len(priorities)+ 1): 
     items= (yield k, q.top_one()) 
     if not None is items: 
      q.re_prioritize(items, prioritizer) 

生産：

今

In []: gen_tst()() 
Out[]: [2, 3, 4, 5, 1, 0] 
In []: t= gen_tst(123) 
In []: %timeit t() 
10 loops, best of 3: 26 ms per loop 

をプライオリティキューをrepriorizatingとき、私の質問は、heapify(.)への呼び出しを回避する任意のデータ構造が存在しませんさ？私はここで速度のためにメモリを交換するつもりですが、純粋なPythonで実装することは可能です（私の素朴な実装よりもはるかに良いタイミングが明らかです）。

更新：
あなたは、特定の場合に、より理解してもらうためには、最初の（バッチ）を押して、その後、すべてのキューの意志から（POP）フェッチした後、何のアイテムがキューに追加されていないことを前提としていますおおよそこのスキームのようrepriorizationsの数を生成しない：

• 0 * n、めったに
• 0.05 * n、典型的
• n、めったに

ここで、nは、キュー内のitemsの現在の番号です。したがって、どのラウンドでも、再配置するアイテムは、相対的に少数しかありません。だから私は、このパターンを悪用できるデータ構造が存在することが期待されているため、ヒープ不変量を満たすために、すべてのラウンドで必須のheapify(.)を実行するコストを上回っています。

アップデート2：
これまでのところ、heapify(.)アプローチが実際に（相対的に言って）非常に効率的であると思われます。私が知ることができたすべての選択肢は、heappush(.)を利用する必要があり、当初期待していたより高価なようです。 （とにかく、問題の状態がこのように残っているなら、私はpython領域からより良い解決策を見つけなければなりません）。

Answer 1

新しい優先順位付け関数は以前のものと関係がない可能性があるので、新しい順序付けを取得するためにはコストを支払う必要があります（新しい順序付けで最小要素を見つけるには最小O（n）です）。小規模で固定数の優先順位付け関数を持ち、それらの間で頻繁に切り替える場合は、各関数ごとに独立したヒープを保持することで利益を得ることができます（ヒープではありませんが、ヒープの真ん中）。