0
我需要实现自定义优先级队列，而不使用PriorityQueue形式的Java.Util ...我有三种基本方法：插入，删除和清除。所有的操作必须在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（日志N）是内置库实现的。我假设你已经阅读了内置库，因为它有源代码和文档....你是否真的需要实现Comparable？为什么你会使用未分类的集合，即Stack作为底层结构？ –
'PriorityQueue'在内部使用[heap]（https://en.wikipedia.org/wiki/Heap_（data_structure））。 – Jeffrey
Stack不是一个好主意，也许arrayList会更好？但是我正面临着操作算法的问题...... – Gustavo