34762


Java SEコアAPIに次の条件を満たすコンテナクラスは用意されているでしょうか。

(1)重複要素を許す  
(2)最大値/最小値の取得がO(1)  
(3)任意の要素の削除がO(log(n))

STLでは[`multiset`](http://www.cplusplus.com/reference/set/multiset/)がこれらの性質を満たしています。一方Javaでこのようなクラスを探してみたところ、近いものとして[`PriorityQueue`](http://docs.oracle.com/javase/jp/8/docs/api/java/util/PriorityQueue.html)と[`TreeSet`](http://docs.oracle.com/javase/jp/8/docs/api/java/util/TreeSet.html)が挙がりました。
しかし前者は削除に線形時間かかり、後者は重複要素を許さないため条件に合いませんでした。

`TreeSet`とタプルを使えば同じことを実現できると思いますが、先に挙げた性質を満たすクラスがあるかどうかを知りたいです。


CC BY-SA 3.0
2017-05-16T12:30:34.557
34757
2017-05-16T14:01:21.433
13199
question
java
Javaで削除効率の良い優先度付きキューとして使えるクラスはありますか？


TreeMapを使えばどうですか？やりたいことに一番近いんじゃないかなと。

[code]

    TreeMap<Integer, Integer> treeMap = new TreeMap<>();
    
    // 要素の追加
    Integer n = treeMap.get(i);
    if (n == null) {
      n = 0;
    }
    treeMap.put(i, n + 1);
    
    // 最大値
    treeMap.lastKey();
    
    // 最小値
    treeMap.firstKey();
    
    // 削除
    Integer n = treeMap.get(i);
    if (n != null) {
      treeMap.put(i, n - 1);
    }
    
    // 存在確認
    Integer n = treeMap.get(i);
    boolean hasValue = (n != null && n > 0);
    
[/code]

オーダーの計算はあまり得意じゃないので雰囲気ですが、ソースを見る感じと木構造というのを考えると要素の操作はO(log(n))になりそうです。  
<http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/TreeMap.java>


CC BY-SA 3.0
2017-05-16T14:01:21.433
34762
2017-05-16T14:01:21.433
7655
34757
answer