バランスの取れたバイナリ ツリー (赤黒ツリーなど) を使用して、並べ替えられたインデックスを格納できます。これにより、インデックス全体を毎回並べ替える場合よりも更新が速くなります。
Javaっぽい疑似コードを使用すると、これは次のようになります
Tree tree;
Node {
int priority;
incrementPriority() {
priority = priority + 1;
if(priority > tree.nextHighestNode(this)) {
tree.remove(this);
tree.add(this);
}
}
decrementPriority() {
priority = priority - 1;
if(priority < tree.nextLowestNode(this)) {
tree.remove(this);
tree.add(this);
}
}
}
ノードの優先度を変更することで、そのノードが無効なツリーの場所にあることを意味する場合 (つまり、次に高いノードであるべきものよりも高いか、次に低いノードであるべきものよりも低いことを意味します)、そのノードは削除され、再度実行されます。ツリーに追加されます (リバランス自体を処理します)。挿入は O(log(n)) ですが、通常 (挿入/削除がない場合) 優先度の更新は一定時間の操作です。
赤黒木はバランスの取れた二分木が通常どのように実装されるかですが、代替手段があります。たとえば、Tango 木はオンライン実装であるため、ここではおそらくより適切です。最大の問題は同時実行性にあります。理想的には、ある種の AtomicInteger (アトミック インクリメントとデクリメントを許可します。かなりの数の言語がこのようなものを持っています) を使用して、ノードの優先度フィールドを実装できるようにする必要があります。フィールドを変更するたびにロックする必要はありませんが、優先度を隣接ノードの優先度とアトミックに比較することは困難です。
別の方法として、配列または連結リストにすべてを格納し、優先順位が変更されたときに隣接する要素を交換することができます。要素はO(log(n))であり、隣接する2つの配列/リスト要素を交換するのは一定時間です。唯一の問題は、配列のすべての要素をシフトする必要があるため、まったく新しい要素を追加すると配列にコストがかかることです。アイテムを挿入する正しい場所が見つかるまでリストをトラバースする必要があるため、リストでも O(n) になりますが、隣接するものをシフトする必要がないため、これはおそらく配列よりも望ましいです要素 (これにより、必要なロックの量が減ります)。