scala - Scalaで2つの優先キューを「同期」させることは可能ですか？

Question

2種類の優先順位を持つオブジェクトのセットがあります。それぞれの順序で2つのPriorityQueueを作成できます。問題は、それらの1つから要素をデキューしても、明らかに他の要素から消えないことです。

「同期」して2つのキューを作成して、要素が一方から削除されると、もう一方から削除されるようにすることは可能ですか？

Answer 1

これにより、特別な種類のデータ構造が保証されます。標準ライブラリで利用可能な標準の「ボンネットの下のバイナリ ヒープ」優先度キューは、必要な要素が他のバイナリ ヒープの「どこ」にあるかわからないため、このトリックを実行できません。

Dijkstra のアルゴリズムまたは A* を実装しようとすると、同様の問題が発生します。そこで機能するトリックは、2 つの順序付けられたツリーをキューのように使用することです。最初の要素をポップして、別のツリーで検索することができます。

Answer 2

対数演算が必要ない場合は、二重リンクリストをキューとして使用してください。これらはFIFOを保証しませんが、必要なものを提供します。

それらのうちの2つを1つのクラスに簡単にラップできます。