Package de.pakad.adt

Class Heap<E>

java.lang.Object
de.pakad.adt.Heap<E>
Type Parameters:
E - Typ der gespeicherten Elemente
public class Heap<E> extends Object
Heap implementiert einen binären Heap (Prioritätswarteschlange) auf Basis eines Arrays.

Die Ordnung der Elemente wird vollständig durch einen Comparator festgelegt, der beim Erzeugen des Heaps übergeben wird.

Der Heap erfüllt die Heap-Eigenschaft: Für jeden Knoten p und seine Kinder c gilt comp.compare(p, c) <= 0.

Die Implementierung verwendet ein dynamisch wachsendes Array und realisiert einen vollständigen binären Baum in impliziter Form.

Java-Version: 17 oder höher

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

  • Constructor Summary

    Constructors
    Constructor
    Description
    Heap(Comparator<? super E> comp, int capacity)
    Erzeugt einen leeren Heap mit der angegebenen Anfangskapazität und der angegebenen Vergleichsfunktion.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    empty()
    Prüft, ob der Heap leer ist.
    E
    peek()
    Liefert das oberste Element des Heaps, ohne es zu entfernen.
    E
    pop()
    Entfernt und liefert das oberste Element des Heaps.
    void
    push(E x)
    Fügt ein neues Element in den Heap ein.
    int
    size()
    Liefert die Anzahl der im Heap gespeicherten Elemente.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • Heap

      public Heap(Comparator<? super E> comp, int capacity)
      Erzeugt einen leeren Heap mit der angegebenen Anfangskapazität und der angegebenen Vergleichsfunktion.
      Parameters:
      comp - Vergleichsfunktion zur Ordnung der Elemente
      capacity - Anfangskapazität des internen Arrays
      Throws:
      IllegalArgumentException - wenn capacity < 1 ist
      NullPointerException - wenn comp == null ist

  • Method Details

    • empty

      public boolean empty()
      Prüft, ob der Heap leer ist.
      Returns:
      true, wenn der Heap keine Elemente enthält, sonst false

    • size

      public int size()
      Liefert die Anzahl der im Heap gespeicherten Elemente.
      Returns:
      Anzahl der Elemente

    • push

      public void push(E x)
      Fügt ein neues Element in den Heap ein.

      Das Element wird zunächst am Ende eingefügt und anschließend durch siftUp an die korrekte Position verschoben, sodass die Heap-Eigenschaft erhalten bleibt.

      Laufzeit: O(log n)

      Parameters:
      x - einzufügendes Element
      Throws:
      IllegalArgumentException - wenn x == null ist

    • peek

      public E peek()
      Liefert das oberste Element des Heaps, ohne es zu entfernen.

      Das oberste Element ist dasjenige mit der höchsten Priorität gemäß der Vergleichsfunktion.

      Laufzeit: O(1)

      Returns:
      oberstes Heap-Element
      Throws:
      NoSuchElementException - wenn der Heap leer ist

    • pop

      public E pop()
      Entfernt und liefert das oberste Element des Heaps.

      Das letzte Element wird an die Wurzel verschoben und anschließend durch siftDown an die korrekte Position gebracht.

      Laufzeit: O(log n)

      Returns:
      entferntes oberstes Heap-Element
      Throws:
      NoSuchElementException - wenn der Heap leer ist