Priority Queue

[Pauli85]

Hallo,
ich soll eine Klasse schreiben, die eine Priority Queue darstellt. Diese soll das Interface Queue implementieren und zwei Konstruktoren haben, einen ohne Parameterliste, der die Elemente in natürlicher Reihenfolge abspeichert, und einen der einen Comparator übergeben bekommt. Außerdem sollen die Elemente in einer ArrayList gespeichert werden.
So weit so gut. Ich habe aber momentan noch das Problem, dass ich nicht weiß wie ich die Prioritäten speichern soll. Das Element mit der höchten Priorität kommt ja ganz nach vorne. Wenn ich jetzt ein Element hinzufüge, brauche ich ja nur zu prüfen, ob die Priorität höher als das erste Element ist oder nicht und es dann ggf. als erstes Element hinzufügen. So habe ich immer das Element mit der höchsten Priorität ganz vorne. Aber was ist, wenn das erste Element gelöscht wird? Woher weiß ich dann ohne die ganze Liste durchzugehen, welches das Element mit der zweit höchsten Priorität ist?
Ich bräuchte also eine Idee um die Prioritäten zu verwalten.

Vielen Dank & Grüße

 

[HimBromBeere]

Du musst doch sowieso durch jedes Element der Liste durchgehen, um sie neu zu priorisieren. Dann machste das in einem Aufwasch.

Noch einfacher wär´s natürlich, wenn du die Priorität einfach als Index einer Liste verwendest. Dann löschst du z.B. einfach das Element der Priorität 1 (also Index 1), der Rest "rutscht doch sowieso nach" (sprich Index 1 ist jetzt das, was vorher Index 2 war usw.).

Kenne mich mit Queues nicht wirklich aus, kann sein, dass es da auch bessere Methoden für gibt.

 

[X5-599]

Nebenbei, ist das Queue Interface das java.util.Queue Interface? Oder etwas eigenes?
Ist hier wohl aber egal...

Da du was von Comparator geschrieben hast, könnte man doch einfach einen schreiben der die Priorität aus den Objekten liest und verarbeitet.

public class MyObject
{
  private int priority;
  public int getPriority()
  {
    return priority;
  }
}

In deiner Queue Klasse dann eine add(MyObject m) Methode die einfach das Objekt in eine ArrayList packt (simples add()) und danach per Arrays.sort(arrayListe.toArray(), myObjectComparator) die Liste sortiert.

Habs jetzt nicht getestet und auch nur gerade aus dem Kopf so hingeschrieben. 😉 Vermutlich bekommt man bei "arrayListe.toArray()" noch Ärger weil nen Object[] zurückkommt und kein MyObject[]... Wie gesagt: Nicht getestet.

 

[Pauli85]

Du musst doch sowieso durch jedes Element der Liste durchgehen, um sie neu zu priorisieren. Dann machste das in einem Aufwasch.

Also ich hab das so verstanden, dass der Vorteil der Queue der ist, dass man nicht jedes Element iterativ durchgehen muss und sich so Zeitaufwand spart. Deshalb sind die Elemente in der Liste auch nicht sortiert. Ich habe hier ein Beispiel aus "Java ist auch eine Insel":

PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
queue.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8 ) );
System.out.println( queue );  // [1, 2, 3, 9, 3, 8]
queue.remove();
System.out.println( queue );  // [2, 3, 3, 9, 8]
queue.remove();
System.out.println( queue );  // [3, 8, 3, 9]
queue.remove();
System.out.println( queue );  // [3, 8, 9]
queue.remove();
System.out.println( queue );  // [8, 9]
queue.remove();
System.out.println( queue );  // [9]
queue.remove();
System.out.println( queue );  // []

Dort ist die Liste ja auch nicht sortiert, trotzdem steht jedesmal das Element mit der höchten Priorität ganz vorne. Und wie ich darauf komme weiß ich nicht.
Das mit dem Comparator im Konstruktor war so gemeint, dass der Defaultkonstruktor verwendet wird, falls es sich um Typen handelt die comparable sind, und falls Typen verwendet werden die nicht comparable sind (z.B. eigene Typen/Klassen) muss man einen Comparator mitübergeben.

Grüße

 

[X5-599]

Also entweder in deiner Objekt Klasse das Comparable Interface imlementieren oder einen Comparator schreiben der mit deiner Objekt Klasse umgehen kann.

Ist dein Problem jetzt die Implementierung des Comparable Interfaces bzw. des Comparators?

 

[Ullenboom]

Die Insel schreibt dazu noch ein bisschen mehr: Galileo Computing :: Java 7 - Mehr als eine Insel - 3 Datenstrukturen und Algorithmen

 

[Joew0815]

Ich wurde mir die einzelnen Prioritäten als Enum definieren:

enum Priority
{
	ECHTZEIT,
	SEHR_HOCH,
	HOCH,
	NORMAL,
	NIEDRIG,
	SEHR_NIEDRIG,
	LEERLAUF
}

Die Queue hat leider nur eine [add] Funktion mit einem Parameter:

public class QueueItem
{
	private final Priority prio;
	private final Object item;

	public QueueItem(Priority prio, Object item)
	{
		super();
		this.prio = prio;
		this.item = item;
	}

	public Priority getPrio()
	{
		return prio;
	}

	public Object getItem()
	{
		return item;
	}
}

Und dann die Objekte in eine Map legen:

// java.util.Map
// java.util.HashMap
private final Map<Priority, List<QueueItem>> items = new HashMap<Priority, List<QueueItem>>();

	public void add(final QueueItem item)
	{
		// Hier wurde schon fuer jede Prio eine List i Konstruktor erstellt
		final List<QueueItem> temp = this.item.get(item.getPrio());
		temp.add(item);
	}
	
	public void add(final QueueItem item)
	{
		// Hier wird die Liste fuer die Prio erstellt, wenn sie gebaucht wird
		List<QueueItem> temp = this.items.get(item.getPrio());
		if(temp == null)
		{
			temp = new ArrayList<QueueItem>();
			this.items.put(item.getPrio(), temp);
		}
		temp.add(item);
	}

Vorteil:
Ich kann mir alle Objekte mit einer bestimmten Priorität Ausgeben
Ich muss nicht bei jedem add sortieren