要素を更新した後にjava.util.PriorityQueueを再調整する

Question

いくつかのオブジェクトへの参照を含むPriorityQueueがあります。最初に要素を優先順位キューに挿入すると、順序はデータ構造によって維持されます。削除操作の後で、私は優先度キューによって保持されている参照のいくつかを更新します。理想的には、これは優先順位キューの再調整操作を必要としますが、選択された参照を外部的に変更しているので明白ですが、再修飾はトリガーできません。だから、キュー内の任意の要素に対する変更があっても、高速抽出のようなヒープの利点を得るための最良の方法は何ですか？私はより良いデータ構造が必要ですか？

具体的には、Javaでフィボナッチヒープのようなものを実装する必要があります。 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 利用可能ですか？

Answer 1

ヒープではなく複製要素を使用できる独自のツリーを使用できます。 さらに簡単に、TreeMap<PriorityKey, LinkedHashSet<Value>>を使用できます。セットの場合

put(priority, new LinkedHashSet())マップのうち優先順位を除去する必要がある以外は、任意の要素が類似して除去、戻りヌル得れば

• 添加は、get(priority).add(value)ある： すべての操作はO（ログpriorityType）であります空の。あなたが削除して、要素を追加する必要が優先順位を変更する必要がまだあれば

  Entry<PriorityKey, LinkedHashSet<Value>> e = map.firstEntry(); 
  if (e==null) return null; 
  Iterator<Value> i = e.getValue().iterator(); 
  Value v = i.next(); //must always have at least one element. 
  i.remove(); 
  if (!i.hasNext()) map.remove(e.getKey()); 
  return v; 
  

  から

• poll（）は

です。

Answer 2

「最高」または「最低」要素の簡単な識別、挿入とアクセスの高速化、および値の簡単な更新が可能なNavigableMapが必要なのかもしれません。

http://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html

のTreeMapはNavigableMapのを実装し、したがってfirstEntry/lastEntry方法、および多くを提供します。