Home meiner WebpräsenzStartseite
Das Menü auf einem Blick!Sitemap
Downloads vorliegender WebSiteDownloads
Hilfeseite vorliegender HomepageHilfe
Erscheinungsvermerk vorliegender HomepageImpressum
Informatik 5 Menüunterpunkte
Algorithmen
4 Menüunterpunkte
Datenstrukturen
3 Menüunterpunkte
Stack
Queue
2 Menüunterpunkte
Dequeue
PriorityQueue
Tree
Ein Menüunterpunkt
Software−Engineering
3 Menüunterpunkte
Programmiersprachen
6 Menüunterpunkte
Künstliche Intelligenz
2 Menüunterpunkte
Schach 9 Menüunterpunkte9 Menüunterpunkte
Privates 8 Menüunterpunkte8 Menüunterpunkte
Inhalt 8 Menüunterpunkte8 Menüunterpunkte










PriorityQueue
Eine Warteschlange nach dem Motto: Je wichtiger, desto eher!
1 Einführung
2 Implementierung
3 Beispiel
Einführung

Definition
Die PriorityQueue ist eine prioritätsorientierte Warteschlange, die stets das Element mit höchster Priorität zurückgibt (remove).
Die Elemente sind nicht mehr gleichberechtigt wie bei der Standard-Warteschlange mit dem FIFO-Prinzip, sondern jedes Element besitzt sozusagen ein Rangabzeichen: je höher der Rang (Priorität), desto weiter vorne wird das Element in die Warteschlange eingereiht.
Manche Algorithmen benötigen eine prioritätsorientierte Warteschlange, die stets das Element mit niedrigster Priorität zurückgibt (MinPriorityQueue).
Diese Idee kann man weiterführen, indem man beispielsweise eine Queue verlangt, die stets den Median zurückgibt (MedianQueue). Es kommt immer darauf an, welche Datenstruktur der Algorithmen-Entwickler gerade benötigt.
Mögliche Schnittstelle: PriorityQueue
1
2
3
4
5
6
7
8
9
10
11
12
13		interface PriorityQueue {

  /* Prüft, ob die PriorityQueue leer ist. */
  public boolean isEmpty();

  /* Fügt ein Element, welches mit den anderen Elementen
     bzgl. der Priorität verglichen werden kann, in die Queue ein. */
  public void insert(Comparable element);

  /* Löscht das Element mit höchster bzw. niedrigster Priorität heraus
     und gibt es zurück. */
  public Comparable remove();
}
Beispiel
Ich zum Beispiel kaufe zu passenden Gelegenheiten meiner Tochter Bonbons, die ich zuhause in die Bonbontüte meiner Tochter gebe. Immer wenn meine Tochter ein Bonbon in dieser Tüte sucht, nimmt sie stets jenes, welches durch Aussehen und Größe den besten Geschmack verspricht.
Gäbe es nun eine prioritätsorientierte Bonbontüte, dann würde das beste Bonbon von den Bonbons in der besagten Tüte stets oben auf liegen — sowas wäre doch fabelhaft! :−)
Allerdings müsste meine Tochter diese Tüte zunächst nach ihrem eigenen Geschmack konfigurieren.
Implementierung

Im Wesentlichen gibt es drei unterschiedliche Strategien eine prioritätsorientierte Warteschlange zu realisieren:
1Man steckt die ganze Arbeit in die Einfügeoperation.
Die Elemente werden beim Einfügevorgang gemäß ihrer Priorität in die interne Liste eingereiht, O(n). Beim Herausnehmen wird das höchste Grenzelemente der internen Liste zurückgegeben, O(1).
2Alternativ steckt man die ganze Arbeit in die Remove-Operation, dabei drehen sich die Laufzeitkomplexitäten um.
Beim Einfügen wird das neue Element der internen Liste lediglich angefügt, O(1). Wobei beim Herausnehmen das Element mit höchster Priorität erst ermittelt werden muss, O(n).
3Die PriorityQueue muss intern nicht als Liste realisiert werden, sie kann auch mit der hierarchischen Datenstruktur Heap realisiert werden. Die Laufzeit der Mutator-Operationen (insert und remove) benötigen jeweils logarithmische Laufzeit, also O(log n).
Realisierung der PriorityQueue mittels LinkedList (Fall 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31		import java.util.LinkedList;

public class LinkedListPriorityQueue implements PriorityQueue {

  private LinkedList buffer;

  public LinkedListPriorityQueue() {
    this.buffer = new LinkedList();
  }

  public boolean isEmpty() {
    return (this.buffer.size() <= 0);
  }

  public void insert(Comparable element) {
    if (this.isEmpty()) this.buffer.addFirst(element);
    else {
      for (int i = 0; i < this.buffer.size(); i++) {
        Comparable listElement = (Comparable)this.buffer.get(i);
        if (element.compareTo(listElement) >= 0) {
          this.buffer.add(i, element);
          break;
        }
      }
    }
  }

  public Comparable remove() {
    return (Comparable)this.buffer.removeFirst();
  }
}
Im Folgenden verwendet die PriorityQueue die baumartige Datenstruktur ArrayHeap, welche unter Heap implementiert ist. Die Funktionalität der PriorityQueue steckt bereits im ArrayHeap, deshalb handelt es sich in der folgenden Klasse um einen Wrapper, der alle Methoden an entsprechende Methoden des Heaps weiterleitet.
Realisierung der PriorityQueue mittels Heap (Fall 3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20		public class HeapPriorityQueue implements PriorityQueue {

  private Heap buffer;

  public HeapPriorityQueue() {
    this.buffer = new ArrayHeap();
  }

  public boolean isEmpty() {
    return this.buffer.isEmpty();
  }

  public void insert(Comparable element) {
    this.buffer.insert(element);
  }

  public Comparable remove() {
    return this.buffer.remove();
  }
}
Anmerkung
Seit Java 1.5 ist die PriorityQueue schon in die API aufgenommen:
java.util.PriorityQueue<E>
Die Komplexität beträgt sowohl für das Einfügen als auch für das Entfernen O(log(n)). Wer mit Java 1.5 entwickelt, muss die PriorityQueue nicht mehr selbst implementieren. Es sei denn, sie müssen die Komplexitäten aufgrund von Geschwindigkeitszusicherungen ändern.
Beispiel

Die PriorityQueue ist eine Datenstruktur, mit der Elemente stets in richtiger Reihenfolge ausgegeben werden können. Im folgenden Beispiel werden die Zeichenketten absteigend ausgegeben (MaxPriorityQueue). Möchte man eine aufsteigende Ausgabe der Zeichenketten, dann kann man für diesen Fall eine MinPriorityQueue implementieren; dafür kann genau dasselbe Interface benutzt werden.
Beispiel: Sortieren von Strings
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31		public class TestPriorityQueue {

  public static void main(String[] args) {

    PriorityQueue prioQueue = new LinkedListPriorityQueue();

    prioQueue.insert("Asterix");
    prioQueue.insert("Obelix");
    prioQueue.insert("Idefix");
    prioQueue.insert("Miraculix");
    prioQueue.insert("Majestix");
    prioQueue.insert("Gutemine");
    prioQueue.insert("Troubadix");
    prioQueue.insert("Automatix");
    prioQueue.insert("Verleihnix");

    while (!prioQueue.isEmpty()) System.out.println(prioQueue.remove());
  }
}

/* Ausgabe> java TestPriorityQueue
Verleihnix
Troubadix
Obelix
Miraculix
Majestix
Idefix
Gutemine
Automatix
Asterix
*/
Allgemein

Diese Seite ist Bestandteil der Domäne www.stefan−baur.de und heißt PriorityQueue. Die letzte Änderung erfuhr diese Seite am Sonntag, den 15. März 2009 von Stefan K. Baur. Zuletzt wurde sie von Ihnen am Mittwoch, den 8. September 2010 um 3:50 Uhr im Internet besucht. Sie gelangen zur vorliegenden Seite, wenn Sie ausgehend von der Startseite über dem Hauptmenü wie folgt navigieren:
Startseite
Informatik
Datenstrukturen
Queue
PriorityQueue
Wenn Sie die vorliegende Seite ausdrucken möchten, nutzen Sie dazu die Printversion.
Autoren

Werden Sie Autor vorliegender Homepage, informieren Sie sich unter Autoren.
Siehe auch ...

Queue
Eine listenähnliche Datenstruktur mit dem FIFO-Prinzip heißt Queue oder Warteschlange.
Heap
Eine hierarchische Datenstruktur mit der ordnungserhaltenden Eigenschaft: Vater ist nie kleiner als seine Kinder.
Look & Feel

Das aktuelle Design trägt den Namen „Design 2007”.
Falls Ihnen jedoch das aktuelle Design nicht zusagen sollte, so stehen Ihnen noch andere, alternative Designs zur Verfügung:
Design 2010
Design 2009
Design 2008
Design 2006
Design 2005
Design 2004
Copyright

Vorliegender Webauftritt wurde in mühevoller Kleinarbeit von Stefan K. Baur entwickelt.
Copyright (c) 2004-2010 Stefan K. Baur
Home meiner WebpräsenzStartseite
Das Menü auf einem Blick!Sitemap
Downloads vorliegender WebSiteDownloads
Hilfeseite vorliegender HomepageHilfe
Erscheinungsvermerk vorliegender HomepageImpressum