Priority Queue mit einem Heap implementieren

Im vorherigen Teil der Tutorialserie haben wir eine Queue mit einem Array implementiert. In diesem letzten Teil der Serie zeige ich dir, wie du eine Priority Queue implementierst – und zwar mit Hilfe eines Heaps.

Zur Erinnerung: Bei einer Priority Queue werden die Elemente nicht in FIFO-Reihenfolge entnommen, sondern entsprechend ihrer Priorität. Das Element mit der höchsten Priorität steht immer am Kopf der Queue und wird zuerst entnommen – unabhängig davon, wann es in die Queue eingefügt wurde.

Was ist ein Heap?

Ein "Heap" ist einen Binärbaum, in dem jeder Knoten entweder größer/gleich seiner Kinder ist ("Max Heap") – oder kleiner/gleich seiner Kinder ("Min-Heap").

Für die Priority Queue in diesem Artikel verwenden wir einen Min-Heap, da die höchste Priorität diejenige mit der niedrigsten Zahl ist (Prio 1 ist in der Regel höher als Prio 2).

Hier ist ein Beispiel, wie so ein Min-Heap aussehen könnte:

Das Element an jedem Knoten dieses Baums ist kleiner als die Elemente seiner beiden Kindknoten:

• 1 ist kleiner als 2 und 4;
• 2 ist kleiner als 3 und 7;
• 4 ist kleiner als 9 und 6;
• 3 ist kleiner als 8 und 5.

Array-Darstellung eines Heaps

Ein Heap können wir in einem Array speichern, indem wir dessen Elemente zeilenweise – von links oben nach rechts unten – auf das Array abbilden:

Unser Beispiel-Heap sieht als Array wie folgt aus:

Bei einem Min-Heap ist das kleinste Element immer oben, im Array also immer an erster Position. Genau deshalb siehst du, wenn du eine Java-PriorityQueue als String ausgibst, immer das kleinste Element links. Was du siehst, ist die Array-Darstellung des der PriorityQueue zugrunde liegenden Min-Heaps.

Mit den folgenden Codezeilen lässt sich das gut demonstrieren:

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.addAll(List.of(4, 7, 3, 8, 2, 9, 6, 5, 1));
System.out.println("priorityQueue = " + priorityQueue);
Code-Sprache: Java (java)

Das Ausgabe des Programms lautet:

priorityQueue = [1, 2, 4, 3, 7, 9, 6, 8, 5]
Code-Sprache: Klartext (plaintext)

Das kleinste Element ist ganz links. Und wenn du genau hinschaust, erkennst du, dass die Zahlen exakt die gleiche Reihenfolge haben wie in der grafischen Array-Darstellung oben. Der Min-Heap der im Beispiel erstellten PriorityQueue ist genau der, den ich zu Beginn des Artikels abgebildet habe.

Priority Queue mit einem Min-Heap – Der Algorithmus

OK, das kleinste Element steht immer ganz links. Damit ist schon mal klar, wie die peek()-Operation zu funktionieren hat: sie muss einfach das erste Element des Arrays zurückgeben.

Doch wie wird so ein Heap aufgebaut? Wie funktionieren enqueue() und dequeue()?

Einfügen in den Min-Heap: Sift Up

Um ein Element in einen Heap einzufügen, gehen wir wie folgt vor:

1. Wir fügen das neue Element als letztes Element in den Baums ein, d. h.:
   • Ist der Baum leer, fügen wir das neue Element als Wurzel ein.
   • Wenn die unterste Ebene des Baums nicht voll ist, fügen wir das neue Element neben dem letzen Knoten der untersten Ebene ein.
   • Ist die unterste Ebene voll, dann hängen wir den Knoten unter den ersten Knoten der untersten Ebene.
2. Solange der Elternknoten des neuen Elements kleiner ist als das Element selbst (was die Min-Heap Regel verletzten würde), vertauschen wir den neuen Knoten mit seinem Elternknoten.

Schritt 1 hört sich kompliziert an, bedeutet in der Array-Darstellung aber lediglich, dass das neue Element an die erste freie Stelle des Arrays gesetzt wird. Schritt 2 sorgt dafür, dass am Ende der Operation wieder jedes Element kleiner ist als seine Kinder.

Das Beispiel im folgenden Abschnitt demonstriert die beiden Schritte.

Einfügen in den Min-Heap: Beispiel

An den folgenden Beispielen zeige ich dir Schritt für Schritt, wie eine auf einem Min-Heap basierende Priority Queue mit den oben gezeigten Beispielwerten (4, 7, 3, 8, 2, 9, 6, 5, 1) gefüllt wird. In jedem Schritt zeige ich den Min-Heap jeweils in Baum- und in Array-Darstellung.

1. Element – Einfügen der 4 in eine leere Priority Queue

Das erste einzufügende Element wird zum Wurzelknoten des Baumes; im Array wird es an die erste Position gesetzt:

2. Element – Einfügen der 7

Die 7 wird unter den ersten Knoten der untersten Ebene eingehängt – also links unter die Wurzel. Im Array wird sie einfach angehängt:

Die 7 ist größer als ihr Elternknoten 4 – damit ist die Einfügeoperation abgeschlossen. Das kleinste Element steht nach wie vor am Anfang der Priority Queue.

3. Element - Einfügen der 3

Die 3 wird neben dem letzten Knoten der untersten Ebene, also rechts unter der 4, angehängt. Im Array kommt sie ans Ende:

Die 3 ist kleiner als ihr Elternknoten. Die Regeln des Min-Heaps sind also verletzt. Wir stellen den Min-Heap wieder her, in dem wir die 3 mit der 4 tauschen:

Damit haben wir wieder einen validen Min-Heap.

Wir überspringen die 8, 2, 9, 6 und 5 (diese werden analog eingefügt) und kommen zum...

9. Element – Einfügen der 1

Zuletzt fügen wir die 1 am Ende der Queue (und des Arrays) ein:

Die 1 ist größer als ihr Elternknoten 5; unser Baum ist also kein gültiger Min-Heap mehr. Um ihn zu reparieren, tauschen wir zunächst die 1 mit der 5:

Die 1 ist ebenfalls größer als ihr neuer Elternknoten 3; somit tauschen wir erneut:

Die 1 ist auch größer als die Wurzel 2, also tauschen wir ein drittes Mal:

Da die 1 nun an der Wurzel angelangt ist, ist die Operation beendet. Der Baum ist wieder ein Min-Heap. Das kleinste Element steht an der Wurzel des Baumes (und am Anfang des Arrays).

Dieses Hochreichen des eingefügten Elements auf die eben gezeigte Weise bezeichnet man als "Sift Up".

Vereinfachter Sift-Up-Algorithmus

Tatsächlich brauchen wir uns gar nicht die Mühe zu machen das neue Element am Ende einzufügen, um es dann schrittweise mit seinem Elternknoten zu tauschen. Stattdessen können wir uns das neue Element merken, die größeren Elternelemente nach unten schieben und zum Schluss das neue Element direkt an seine Zielposition setzen.

Die folgenden Grafiken zeigen das Einfügen der 1 nach dem vereinfachten Algorithmus.

Die 1 ist kleiner als der Elternknoten des freien Knotens. Wir schieben daher die 5 in den freien Knoten:

Die einzufügende 1 ist ebenso kleiner als die 3; wir schieben die 3 nach unten:

Die 1 ist kleiner als die 2; wir schieben auch die 2 nach unten:

Wir können keine weiteren Elemente nach unten schieben und setzen das einzufügende Element, die 1, auf den freigewordenen Wurzelknoten (oder das erste Feld des Arrays):

Damit ist die Sift-Up-Operation abgeschlossen.

Das Einfügen eines Elements in die Priority Queue (bzw. in den Min-Heap) mag beim ersten Durchlesen sehr komplex erscheinen. Falls du es nicht verstanden hast, mach eine kurze Pause und wiederhole das Kapitel noch einmal, bevor du zur Dequeue-Operation fortschreitest.

Entnahme aus dem Min-Heap: Sift Down

Wir wissen, dass das kleinste Element immer an der Wurzel des Baumes steht (oder am Anfang des Arrays).

Um es zu entnehmen, gehen wir wie folgt vor:

1. Wir entfernen das Wurzelelement aus dem Baum.
2. Wir verschieben den letzten Knoten der letzten Ebene des Baumes (das entspricht dem letzten Element des Arrays) an die freigewordene Wurzelposition.
3. Solange dieser Knoten größer ist als eines seiner Kinder (was die Min-Heap Regel verletzten würde), vertauschen wir den Knoten mit seinem kleinsten Kindknoten.

Entnahme aus dem Min-Heap: Beispiel

Das folgende Beispiel zeigt, wie wir das Wurzelelement des im letzten Kapitel gefüllten Min-Heaps entnehmen und danach die Min-Heap-Bedingung wiederherstellen.

Als erstes entnehmen wir das Wurzelelement:

Als zweites verschieben wir das letzte Element des Baumes, die 5, an die frei gewordene Wurzel:

Da das neue Wurzelelement, die 5, jetzt größer ist als das kleinste seiner Kinder, die 2, vertauschen wir diese beiden Elemente:

Die 5 ist weiterhin größer als das kleinste ihrer Kinder, die 3. Wir tauschen ein zweites Mal:

Die 5 ist jetzt größer als ihr einziges Kind; die Min-Heap-Bedingung ist damit wiederhergestellt.

An der Wurzel des Min-Heaps (bzw. am Anfang des Arrays) befindet sich jetzt die 2, das neue kleinste Element nach Entnahme der 1.

Das Herunterwandern des an die Wurzel verschobenen Elements bezeichnet man als "Sift Down".

Vereinfachter Sift-Down-Algorithmus

Auch den Sift-Down-Algorithmus können wir vereinfachen. Wir müssen das letzte Element (im Beispiel die 5) nicht erst an die Wurzel schieben, um es dann schrittweise mit seinen Kindern zu tauschen. Wir können auch zuerst die größeren Elemente nach oben schieben und am Ende das letzte Element direkt an seine endgültige Position verschieben.

Die folgenden Grafiken zeigen das Herunterreichen der 5 (oder besser gesagt: des freien Feldes, auf das am Ende die 5 gesetzt wird) nach dem vereinfachten Algorithmus.

Die 5 ist größer als der kleinste Kindknoten der leeren Wurzel, die 2. Wir schieben die 2 nach oben:

Die 5 ist ebenso größer als das kleinste Kind des jetzt freien Platzes, die 3. Wir schieben auch die 3 nach oben:

Die 5 ist nicht größer als das einzige Kind des jetzt freien Platzes, die 8. Wir haben also das Zielfeld für die 5 gefunden und schieben die 5 dorthin:

Wir haben die Min-Heap-Bedingung wiederhergestellt.

Die Sift-Up- und Sift-Down-Operationen mögen komplex erscheinen, sie können allerdings beide mit maximal 10 Zeilen Java-Code implementiert werden. Wie, erfährst du im nächsten Kapitel.

Quellcode für Priority Queue mit Min-Heap

Der folgende Quellcode zeigt, wie man eine Priority Queue mit einem Min-Heap implementiert (Klasse HeapPriorityQueue im GitHub-Repository). Aufgrund der Länge der Klasse zeige ich sie im Folgenden abschnittsweise.

Konstruktoren

Es gibt zwei Konstrukturen: einen, bei dem man die initiale Größe des Arrays angeben kann und einen Default-Konstruktor, der die initiale Kapazität auf zehn setzt:

public class HeapPriorityQueue<E extends Comparable<? super E>> implements Queue<E> {

  private static final int DEFAULT_INITIAL_CAPACITY = 10;
  private static final int ROOT_INDEX = 0;

  private Object[] elements;
  private int numberOfElements;

  public HeapPriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY);
  }

  public HeapPriorityQueue(int capacity) {
    if (capacity < 1) {
      throw new IllegalArgumentException("Capacity must be 1 or higher");
    }

    elements = new Object[capacity];
  }
Code-Sprache: Java (java)

enqueue()

Die enqueue()-Methode prüft zunächst, ob das Array voll ist. Ist das der Fall, ruft sie die grow()-Methode auf, welche das Array in ein neues, größeres Array kopiert:

  @Override
  public void enqueue(E newElement) {
    if (numberOfElements == elements.length) {
      grow();
    }
    siftUp(newElement);
    numberOfElements++;
  }

  private void grow() {
    int newCapacity = elements.length + elements.length / 2;
    elements = Arrays.copyOf(elements, newCapacity);
  }Code-Sprache: Java (java)

Die grow()-Methode habe ich hier stark vereinfacht dargestellt, da der Fokus auf den siftUp()- und siftDown()-Methoden liegen soll.

In der HeapPriorityQueue-Klasse im GitHub-Repository vergrößert die grow()-Methode das Array bis zu einer bestimmten Größe (64 Elemente) um Faktor 2 und erst danach um Faktor 1,5. Außerdem wird dort sichergestellt, dass eine bestimmte Maximalgröße nicht überschritten wird.

Wenn wir sichergestellt haben, dass das Array groß genug ist, rufen wir die siftUp()-Methode auf:

siftUp()

  private void siftUp(E newElement) {
    int insertIndex = numberOfElements;

    while (isNotRoot(insertIndex) && isParentGreater(insertIndex, newElement)) {
      copyParentDownTo(insertIndex);
      insertIndex = parentOf(insertIndex);
    }

    elements[insertIndex] = newElement;
  }

  private boolean isNotRoot(int index) {
    return index != ROOT_INDEX;
  }

  private boolean isParentGreater(int insertIndex, E element) {
    int parentIndex = parentOf(insertIndex);
    E parent = elementAt(parentIndex);
    return parent.compareTo(element) > 0;
  }

  private void copyParentDownTo(int insertIndex) {
    int parentIndex = parentOf(insertIndex);
    elements[insertIndex] = elements[parentIndex];
  }

  private int parentOf(int index) {
    return (index - 1) / 2;
  }
Code-Sprache: Java (java)

Beachte, dass ich versucht habe den Algorithmus so verständlich wie möglich (und nicht so performant wie möglich) zu implementieren. Die parentOf()-Methode wird in jeder Iteration drei Mal aufgerufen: einmal von isParentGreater(), einmal von copyParentDownTo() und einmal direkt.

Eine verbesserten Variante (Klasse OptimizedHeapPriorityQueue im GitHub-Repo, ab Zeile 74) zeigt einen optimierten Algorithmus, der den Elternindex nur ein Mal berechnet.

dequeue()

Die dequeue()-Methode entnimmt das Kopf-Element, entfernt das letzte Element und ruft dann siftDown() auf, das letztendlich dieses letzte Element an seine neue Position verschiebt.

  @Override
  public E dequeue() {
    E result = elementAtHead();
    E lastElement = removeLastElement();
    siftDown(lastElement);
    return result;
  }

  private E removeLastElement() {
    numberOfElements--;
    E lastElement = elementAt(numberOfElements);
    elements[numberOfElements] = null;
    return lastElement;
  }
Code-Sprache: Java (java)

siftDown()

siftDown() ist die komplizierteste Methode, da sie einen Knoten immer mit ggf. zwei Kindknoten vergleichen muss.

  private void siftDown(E lastElement) {
    int lastElementInsertIndex = ROOT_INDEX;
    while (isGreaterThanAnyChild(lastElement, lastElementInsertIndex)) {
      moveSmallestChildUpTo(lastElementInsertIndex);
      lastElementInsertIndex = smallestChildOf(lastElementInsertIndex);
    }

    elements[lastElementInsertIndex] = lastElement;
  }

  private boolean isGreaterThanAnyChild(E element, int parentIndex) {
    E leftChild = leftChildOf(parentIndex);
    E rightChild = rightChildOf(parentIndex);

    return leftChild != null && element.compareTo(leftChild) > 0
        || rightChild != null && element.compareTo(rightChild) > 0;
  }

  private E leftChildOf(int parentIndex) {
    int leftChildIndex = leftChildIndexOf(parentIndex);
    return exists(leftChildIndex) ? elementAt(leftChildIndex) : null;
  }

  private int leftChildIndexOf(int parentIndex) {
    return 2 * parentIndex + 1;
  }

  private E rightChildOf(int parentIndex) {
    int rightChildIndex = rightChildIndexOf(parentIndex);
    return exists(rightChildIndex) ? elementAt(rightChildIndex) : null;
  }

  private int rightChildIndexOf(int parentIndex) {
    return 2 * parentIndex + 2;
  }

  private boolean exists(int index) {
    return index < numberOfElements;
  }

  private void moveSmallestChildUpTo(int parentIndex) {
    int smallestChildIndex = smallestChildOf(parentIndex);
    elements[parentIndex] = elements[smallestChildIndex];
  }

  private int smallestChildOf(int parentIndex) {
    int leftChildIndex = leftChildIndexOf(parentIndex);
    int rightChildIndex = rightChildIndexOf(parentIndex);

    if (!exists(rightChildIndex)) {
      return leftChildIndex;
    }

    return smallerOf(leftChildIndex, rightChildIndex);
  }

  private int smallerOf(int leftChildIndex, int rightChildIndex) {
    E leftChild = elementAt(leftChildIndex);
    E rightChild = elementAt(rightChildIndex);
    return leftChild.compareTo(rightChild) < 0 ? leftChildIndex : rightChildIndex;
  }
Code-Sprache: Java (java)

Genau wie siftUp() habe ich auch siftDown() mit Fokus auf Lesbarkeit geschrieben, nicht auf Performance. So werden hier pro Iteration drei Mal die Positionen der Kindelemente berechnet: in isGreaterThanAnyChild(), in moveSmallestChildUpTo() und noch einmal in smallestChildOf().

In der optimierten Klasse OptimizedHeapPriorityQueue werden diese Positionen nur einmal berechnet. Dadurch ist der Code aber auch nicht mehr ganz so leicht zu lesen.

peek(), isEmpty() und zwei Hilfsmethoden

Und zum Schluss noch die peek()- und isEmpty()-Methoden sowie zwei Hilfsmethoden, die verwendet werden, um das Element vom Kopf der Queue oder von einer spezifischen Position zu lesen.

Da wir die Elemente in einem Object-Array speichern, müssen die Array-Elemente nach E gecastet werden. Damit die Casts nicht über den gesamten Quellcode verteilt sind, habe ich das Casten in eine zentrale Stelle, die Methode elementAt(), ausgelagert und dort die "unchecked"-Warnung einmalig unterdrückt.

  @Override
  public E peek() {
    return elementAtHead();
  }

  private E elementAtHead() {
    E element = elementAt(0);
    if (element == null) {
      throw new NoSuchElementException();
    }
    return element;
  }

  private E elementAt(int child) {
    @SuppressWarnings("unchecked")
    E element = (E) elements[child];
    return element;
  }

  @Override
  public boolean isEmpty() {
    return numberOfElements == 0;
  }
}Code-Sprache: Java (java)

Wenn dir der Kopf noch nicht raucht, schau dir auch gerne einmal den Quellcode der PriorityQueue-Klasse des JDK an. Diese kann Elemente nicht nur nach ihrer natürlichen Ordnung sortieren, sondern auch anhand eines dem Konstruktor übergebenen Comparators.

Fazit

Damit endet diese Tutorial-Serie über Queues. In dieser Serie hast du gelernt, wie eine Queue funktioniert, was bounded und unbounded, blocking und non-blocking Queues sind, welche Queue-Implementierungen es im JDK gibt und wie man Queues auf verschiedene Arten selbst implementieren kann.

Wenn dir die Serie gefallen hat, hinterlasse mir gerne einen Kommantar oder teile die Artikel über die Share-Buttons am Ende. Wenn du noch Fragen hast, kannst du sie gerne über die Kommentar-Funktion stellen.

Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.