問題は、2つの異なる方法で一連の値にアクセスすることです。まず、優先順位。単にヒープで実装されています。さらに、各値に1つまたは複数の記号を「タグ付け」して、アイテムのリストにアクセスできるようにする必要があります。検索可能なヒープ構造
これは、2つの異なる構造の同じデータを参照することによって効率的に実装するのに十分簡単です。ただし、これらは密接なキューを形成する必要があります。したがって、一方の構造体を介して削除されたアイテムも、他方の構造体から削除する必要があります。これは、ヒープが非常に適切でない操作です。
任意の位置でノードの検索/削除のパフォーマンスを完全に低下させることなく、1つの値（理想的にはプッシュ/ポップに最適化）で効率的な順序付けを行うことができるデータ構造がありますか？
O（log（n））時間内にバイナリヒープから任意の要素を削除することができます。どのノードも有効な「サブヘープ」として扱うことができますし、すべての場合と同じようにdelete-max（またはdelete-min）操作を使用することができます。
唯一の問題は、削除する方法をどのように知っているかです。私はそれを解決する手段があると思う。ヒープノードへの参照を持つ格納されたクラスのラッパーを使用し、そのノードをラッパーデストラクターから削除します。コレクションから要素を削除したいときは、インデックスを使ってラッパーを削除するだけで、残りの部分を処理します。コレクションに何かを挿入するときは、ラッパー・オブジェクトを作成し、そのヒープ・ノードへの参照を渡す必要があります。
template <class T> class Wrapper {
T data;
HeapNode* index_heap;
Foo* index_tags;
Bar* index_queue;
public: ~Wrapper() {
index_heap->delete_max();
index_tags->delete_foo();
index_queue->delete_bar();
}
};
は、いくつかのC++のコードであります