ScalaのTreeSetとJavaのTreeSet - poll？

Question

の時刻の最高値をJavaのTreeSetで削除する場合は、treeSet.pollFirst()を使用します。これはScalaのmutable.TreeSetクラスに相当するものですか？

とにかく、私が実際に望むのは、removeMax、add、updatePriorityを対数時間で表示できるヒープのような優先順位キューのデータ構造です。 mutable.PriorityQueueは対数時間でdeque（すなわちremoveMax）を私に許可していますが、ログ時に優先順位を更新する方法はありません（私はひっくり返ってスキャンしてアイテムを削除してから再追加する必要があります）線形時間）。同様にmutable.TreeSetは、対数時間で（ハックリ削除と再追加による）優先順位を更新することができますが、removeMax（つまりpollFirst）の操作はありません。どのコレクションコンテナを使用する必要がありますか？私は外部の依存関係を参照しないでください。

Answer 1

あなたはO(log n)あるimmutable.TreeSetでheadとlast方法を、使用することができます。 mutable.TreeSetにも同じメソッドがありますが、効率を上げ、時間を償却するためにオーバーライドされていません（Scala 2.10）。 headメソッドは対数ですが、そのときイテレータをインスタンス化することができます。 lastメソッドは、それを実際にトラバースし、線形の複雑さを持ちます。良いお知らせは、カスタムOrderingで最小または最大のものを制御でき、Ordering.reverseと呼んで既存のOrderingから簡単に取得できることです。

この要素を削除する必要がある場合は、単に-=を使用してください。独自の暗黙的な値クラスを作成して、pollFirstメソッドをツリーセットにピギーバックすることができます。

implicit class MyExtensions[T](ts: mutable.TreeSet[T]) extends AnyVal { 
    def pollFirst(): T = { 
    val elem = ts.head 
    ts -= elem 
    elem 
    } 
} 

Answer 2

だけではなく、提案:)それを使用する、JavaのTreeSetのは、あなたのために働くので、もしあなたが:) JVMにコンパイル場合は、ウェル（スカラ座からのJavaライブラリにアクセスできることを覚えておいてください答え、:)

要件を明確にすることもできます。あなたのupdatePriorityメソッドのパラメータは何ですか？あなたの優先順位を更新しようとしていますか？