0

Java.Util フォームの PriorityQueue を使用せずに、カスタム プライオリティ キューを実装する必要があります。insert、remove、および clear の 3 つの基本メソッドがあります。すべての操作は、一定時間 O (log n) で実行する必要があります。どうすればこれを達成できますか? これらの操作にはどのアルゴリズムを使用すればよいですか? 最後に、ジェネリック値を保持するためにどのタイプのコンテナを使用すればよいですか?

これは私がこれまでに行ったことです...

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();
        }
    }
}

それほど多くはありません..しかし、助けていただければ幸いです!

4

2 に答える 2

1

あなたの「削除」操作が最大の要素を取っていることがわかります。「最大ヒープ」が目的に合っているようです。

https://en.wikipedia.org/wiki/Heap_(data_structure)

于 2016-05-07T15:55:20.433 に答える