Package de.pakad.adt

Class PriorityQueue<T extends Comparable<? super T>>

java.lang.Object
de.pakad.adt.PriorityQueue<T>
Type Parameters:
T - Typ der gespeicherten Elemente; muss Comparable implementieren
All Implemented Interfaces:
Queue<T>
public class PriorityQueue<T extends Comparable<? super T>> extends Object implements Queue<T>
PriorityQueue implementiert eine Prioritätswarteschlange auf Basis eines binären Heaps.

Die Priorität der Elemente ergibt sich aus ihrer natürlichen Ordnung (siehe Comparable). Das jeweils kleinste Element wird als erstes geliefert (Min-PriorityQueue).

Diese Klasse implementiert das Queue-Interface, weicht jedoch von einer klassischen FIFO-Queue ab: Die Reihenfolge der Abarbeitung richtet sich nach der Priorität der Elemente und nicht nach der Einfügereihenfolge.

Intern wird ein Heap verwendet, der mit der natürlichen Ordnung der Elemente initialisiert wird.

Java-Version: 17 oder höher

Author:
Karsten Brodmann (kb@punkt-akademie.de)

  • Constructor Summary

    Constructors
    Constructor
    Description
    PriorityQueue(int capacity)
    Erzeugt eine leere Prioritätswarteschlange mit der angegebenen Anfangskapazität.

  • Method Summary

    Modifier and Type
    Method
    Description
    T
    dequeue()
    Entfernt und liefert das Element mit der höchsten Priorität.
    boolean
    empty()
    Prüft, ob die Prioritätswarteschlange leer ist.
    void
    enqueue(T x)
    Fügt ein Element in die Prioritätswarteschlange ein.
    T
    front()
    Liefert das Element mit der höchsten Priorität, ohne es zu entfernen.
    int
    size()
    Liefert die Anzahl der in der Prioritätswarteschlange gespeicherten Elemente.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • PriorityQueue

      public PriorityQueue(int capacity)
      Erzeugt eine leere Prioritätswarteschlange mit der angegebenen Anfangskapazität.
      Parameters:
      capacity - Anfangskapazität der Queue
      Throws:
      IllegalArgumentException - wenn capacity < 1 ist

  • Method Details

    • enqueue

      public void enqueue(T x)
      Fügt ein Element in die Prioritätswarteschlange ein.

      Die Position des Elements wird entsprechend seiner Priorität (natürliche Ordnung) bestimmt.

      Laufzeit: O(log n)

      Specified by:
      enqueue in interface Queue<T extends Comparable<? super T>>
      Parameters:
      x - einzufügendes Element
      Throws:
      IllegalArgumentException - wenn x == null ist

    • front

      public T front()
      Liefert das Element mit der höchsten Priorität, ohne es zu entfernen.

      Die höchste Priorität besitzt das kleinste Element gemäß der natürlichen Ordnung.

      Laufzeit: O(1)

      Specified by:
      front in interface Queue<T extends Comparable<? super T>>
      Returns:
      Element mit der höchsten Priorität
      Throws:
      NoSuchElementException - wenn die Queue leer ist

    • dequeue

      public T dequeue()
      Entfernt und liefert das Element mit der höchsten Priorität.

      Die höchste Priorität besitzt das kleinste Element gemäß der natürlichen Ordnung.

      Laufzeit: O(log n)

      Specified by:
      dequeue in interface Queue<T extends Comparable<? super T>>
      Returns:
      entferntes Element mit der höchsten Priorität
      Throws:
      NoSuchElementException - wenn die Queue leer ist

    • empty

      public boolean empty()
      Prüft, ob die Prioritätswarteschlange leer ist.
      Specified by:
      empty in interface Queue<T extends Comparable<? super T>>
      Returns:
      true, wenn keine Elemente enthalten sind, sonst false

    • size

      public int size()
      Liefert die Anzahl der in der Prioritätswarteschlange gespeicherten Elemente.
      Returns:
      Anzahl der Elemente