Startseite < Informatik < Algorithmen Datenstrukturen < Stack Queue < Dequeue [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] PriorityQueue > Tree > / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >
PriorityQueue
Eine Warteschlange nach dem Motto: Je wichtiger, desto eher!
Einführung Theorie: PriorityQueue
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
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();
}
⇑ Mögliche Schnittstelle: PriorityQueue ⇑
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 Implementierung: PriorityQueue
Im Wesentlichen gibt es drei unterschiedliche Strategien eine prioritätsorientierte Warteschlange zu realisieren:
  1. Man 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).
  2. Alternativ 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).
  3. Die 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)
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();
  }
}
⇑ Realisierung der PriorityQueue mittels LinkedList (Fall 1) ⇑
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)
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();
  }
}
⇑ Realisierung der PriorityQueue mittels Heap (Fall 3) ⇑
Anmerkung
Seit Java 1.5 ist die PriorityQueue schon in die API aufgenommen:
  1. 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 Anwendungsbeispiel: PriorityQueue
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
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
*/
⇑ Beispiel: Sortieren von Strings ⇑
Startseite   Sitemap   Downloads   Hilfe   Impressum  
Startseite < Informatik < Algorithmen Datenstrukturen < Stack Queue < Dequeue [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] PriorityQueue > Tree > / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >