PriorityQueueによる最大最小スタックの実現
これは、最大スタック、最小スタックを実現する必要があるofferを指す「データストリームの中位数」という問題で発生した問題です.
実装方法は次のとおりです.
ここでPriorityQueueクラスはJDK 1である.5後に提供される新しいデータ構造のインタフェースは、デフォルトでは最小スタックが実装されていますが、そのシーケンサを書き換えることで最大スタックを実現できます.利用する構成方法は、initialCapacityが初期容量を指す、デフォルト値が11であるため書き換え時は11とする.
実装方法は次のとおりです.
PriorityQueue minHeap = new PriorityQueue(); // , 11
PriorityQueue maxHeap = new PriorityQueue(11,new Comparator(){ // , 11
@Override
public int compare(Integer i1,Integer i2){
return i2.compareTo(i1);
}
});
ここでPriorityQueueクラスはJDK 1である.5後に提供される新しいデータ構造のインタフェースは、デフォルトでは最小スタックが実装されていますが、そのシーケンサを書き換えることで最大スタックを実現できます.利用する構成方法は、initialCapacityが初期容量を指す、デフォルト値が11であるため書き換え時は11とする.
PriorityQueue(int initialCapacity, Comparator super E> comparator)