Implementieren Von Java-Priorität-Warteschlange
public class PriorityQueue<T> {
private PriorityNode<T> head, tail;
private int numItems;
public PriorityQueue(){
numItems = 0;
head=null;
tail=null;
}
public void add(int priority, T value){
PriorityNode<T> newNode = new PriorityNode<T>(priority,value);
if(numItems == 0){
head = newNode;
tail = newNode;
}
else{
head.setNext(newNode);
head = newNode;
}
}
}
Wo PriorityNode ist definiert als:
public class PriorityNode<T> implements Comparable<T> {
private T value;
private PriorityNode<T> next;
private int priority;
public PriorityNode(int priority,T newValue){
value = newValue;
next = null;
priority = 0;
}
public PriorityNode(T newValue){
value = newValue;
next = null;
priority = 0;
}
public void setPriority(int priority){
this.priority = priority;
}
public int getPriority(){
return this.priority;
}
public T getValue(){
return value;
}
public PriorityNode<T> getNext(){
return next;
}
public void setNext(PriorityNode<T> nextNode){
this.next = nextNode;
}
public void setValue(T newValue){
value = newValue;
}
@Override
public int compareTo(int pri) {
//TODO Auto-generated method stub
if(this.priority<pri){
return -1;
}
else if(this.priority == pri){
return 0;
}
else{
return 1;
}
}
}
Ich habe eine Menge von Schwierigkeiten mit dem Komparator hier und Implementierung einer priority-queue - bitte zeigen Sie mich in die richtige Richtung.
Es ist nicht ganz klar, was deine Frage ist. Was ist die 'Schwierigkeit'? kompilieren Fehler? unerwartete Ergebnisse?
InformationsquelleAutor Kay | 2010-04-24
Du musst angemeldet sein, um einen Kommentar abzugeben.
Nicht eine Baum-Struktur zur Implementierung einer priority-queue. Verwenden Sie eine heap. Es ist mehr Platz-effizient, braucht weniger Speicher, Zuweisungen, und ist O(log(N)) für die meisten Operationen.
InformationsquelleAutor Marcelo Cantos
Bezüglich der Umsetzung des Komparators, die Umsetzung der
Komparator - <T>
oderVergleichbar<T>
Schnittstelle erfordert, dass derpublic int compareTo(T o)
- Methode überschrieben werden.In der Beispiel-code gegeben, der
compareTo(T)
- Methode ist nicht überschrieben (diecompareTo(int)
Methode definiert ist, aber das ist nicht die gleiche Methode, die Signatur), daher wird es wahrscheinlich führen zu einem compiler-Fehler.InformationsquelleAutor coobird
Ich glaube, Sie machen es ein bisschen zu hart zu dir selbst, eine priority-queue ist, effizient umgesetzt mit array-basierten heaps: einfacher und effizienter (sprich: zusammenhängende Speicher-Bereiche).
InformationsquelleAutor Savino Sguera