0
PriorityQueueフォームJava.Utilを使用せずにカスタムプライオリティキューを実装する必要があります。私は3つの基本的な方法があります：挿入、削除、クリアです。すべての操作は一定時間O（log n）で行わなければなりません。どうすればこれを達成できますか？これらの操作にはどのアルゴリズムを使用する必要がありますか？最後に、汎用値を保持するために使用するコンテナのタイプは何ですか？javaの基本メソッドで一般的なPriorityQueueを実装する方法は？
これは私がこれまで何をやったかである...
public class PriorityQueue<E extends Comparable<? super E>> implements Comparable {
private Stack<E> queue = new Stack<>();
private int size;
public PriorityQueue(int size) {
this.size = size;
}
public PriorityQueue() {
size = 50000;
}
public void insert(E value) {
if (value == null) {
throw new NullPointerException();
}
//how can I insert a value and what container should I use ?
}
public void remove() {
//remove largest
}
public int compareTo(Object o) {
if (o != null && o instanceof PriorityQueue) {
PriorityQueue anotherQueue = (PriorityQueue) o;
return this.size - anotherQueue.size;
} else {
throw new ClassCastException();
}
}
}
はあまりない..しかし、助けをいただければ幸いです！
O（log N）は一定時間ではない。 O（1）は一定時間です。これを一定時間で実装することはできませんが、O（Log N）は組み込みライブラリが達成するものです。私はソースとドキュメントを持っているので、あなたが組み込みのライブラリを読んだと仮定します。あなたは本当にComparableを実装する必要がありますか？なぜソートされていないコレクション、つまりスタックが基本構造として使用されますか？ –
'PriorityQueue'は内部的に[ヒープ]（https://en.wikipedia.org/wiki/Heap_（data_structure））を使用します。 – Jeffrey
スタックは非常に良いアイデアではない、おそらくarrayListは良いでしょうか？しかし、私は操作のためのアルゴリズムの問題に直面しています... – Gustavo