【C++】priority_queueのように最大値を取得しつつ、任意要素の削除もしたい！！

わがままをかなえるシリーズ

以下、競プロでの使用を想定しています。
C++をベースに書いていますが、データ構造についての話なので他の言語でも通用すると思います。

priority_queueで出来ること

priority_queueは、その名の通り優先順位付きキューで、追加された要素のうちの最大値を高速に取得できます。ヒープを用いて実装されています。
priority_queueで出来る操作をまとめた表を示します。ここではpriority_queueの要素数とします。
　

操作	計算量
任意の要素へアクセスする	出来ない
任意の要素を追加する
任意の要素を削除する	出来ない
最大値を取得する
最大値を削除する

　
このように、「追加された要素の集合の中での最大値」を常に高速に求めるのに長けているのが長所です。ただ、追加した要素を途中で削除したくなったとしても、その要素が集合の中のどこに位置するかは外から見てもわかりません。効率よく要素を削除する方法を2つ紹介します。

方法1：priority_queueを2つ用意する

最大値を取得したい要素を追加する（いわゆる普通の用途での）priority_queueと、削除したい要素を追加するためのpriority_queueをそれぞれ用意する方法です。便宜上、前者のpriority_queueを（Queue）、後者を（Remove）として話を進めます。
　
まずは通常の場合と同じようにに要素を追加していきます。ここで、削除したい要素をに追加します。この時点では、まだの中にが含まれています。
　
ではいつ削除されるのかというと、の最大値を取り出そうとしたときです。ここで工夫をして、から最大値を取り出す際に、の最大値も取り出して両者の要素を比較するようにします。もし2つの要素が一致するならば、その要素はに含まれている削除したい要素ということになるので、それぞれのpriority_queueからその要素を削除して、もう一度最大値を取得するようにします。2つの要素が異なるならば、削除したい要素ではないということなので、そのまま取り出した要素を最大値として処理を進めます。
　
この方法のメリットは、priority_queueの性質を保ったまま少し工夫をすることで削除操作もできるようになる点です。次に紹介する方法と比べると、定数倍早いこともメリットとして挙げられます。

方法2：代わりにmultisetを使う

priority_queueと同じ操作を同じような計算量で行えて、さらに削除操作もできるmultisetを使う方法です。multisetは、同じ要素を複数追加できるような多重集合を扱えます。実装には赤黒木という平衡二分木を用いられていることが多いです。

multisetで出来る操作をまとめた表を示します。
　

操作	計算量
任意の要素へアクセスする
任意の要素を追加する
任意の要素を削除する
最大値を取得する
最大値を削除する

　
multisetを使うことで最大値の取得を高速に行いつつ、要素の削除も行えるようになりました。ただし、という同じ計算量に見えますが、実装に用いられているデータ構造が違うため、実際はmultisetの方が定数倍遅いです。極端に遅くなるというわけではないので、実行時間に余裕がある場合はこちらの方法がわかりやすいかと思います。
　
ちなみに、C++のmultisetで要素の削除をする際は少し注意が必要です。削除したい要素をとして

multiset<int> ms;
// 中略
ms.erase(x);

としてしまうと、multisetの中にが複数含まれる場合に、それらが全て削除されてしまいます！！！　複数あるのうち一つだけを削除したいときは、引数に削除したい要素が存在するイテレータを渡してあげれば良くて、例えば

ms.erase(ms.find(x));

と書くことで操作を達成できます。

参考文献

Twitterで実装のアイデアを教えてくださったJoeさん、ぽかーん懐古DPさん、この場を借りて感謝いたします！！

priority_queue - cpprefjp C++日本語リファレンス
C++の日本語リファレンスです。削除操作を行えるメンバ関数は存在しないようです。

c++ - In std::multiset is there a function or algorithm to erase just one sample (unicate or duplicate) if an element is found - Stack Overflow
multisetの削除に関する投稿です。巷では「multisetの罠」と呼ばれているとかいないとか…