Notizen · InformatikDE · Abitur

Datenstrukturen — Listen, Stacks, Queues, Bäume, Graphen, Hashtabellen

Die EPA Informatik fordert die Konstruktion und Analyse linearer wie nichtlinearer Datenstrukturen. Im Mittelpunkt stehen ADT-Definition, Implementation in Java/Python und die Laufzeitanalyse der charakteristischen Operationen.

6Abschnitteca. 19Min Lesezeit3KompetenzenNiveauBasis 2 · Standard 2 · Vertiefung 2Stand 06/2026

T·0333 / 8

Prüfungsprofil

KB-MI · Modellieren und Implementieren — abstrakte Datentypen entwerfen und in Java/Python implementieren.KB-BB · Begründen und Bewerten — Laufzeiten und Speicherbedarf von Datenstrukturen analysieren.KB-SD · Strukturieren und Darstellen — Datenstrukturen grafisch (UML, Diagramm) und algorithmisch dokumentieren.

Operatoren:analysierenimplementierendarstellenbeurteilenmodellieren

grundlegendes Niveau

gA: lineare Liste, Stack, Queue als ADT spezifizieren und mit Arrays oder verketteten Strukturen implementieren; Binärbaum darstellen und traversieren.

erhöhtes Niveau

eA: Bäume balancieren (AVL-Prinzip qualitativ), Graphenalgorithmen (BFS, DFS, Dijkstra) implementieren, Hashtabellen-Kollisionsstrategien (Open Addressing vs. Chaining) gegenüberstellen.

Tiefe

Schrift

Inhalt · 6 Abschnitte

Datenstrukturen — Listen, Stacks, Queues, Bäume, Graphen, Hashtabellen

Lineare Datenstrukturen — Listen, Stacks, Queues#

BasisKMK-EPA-Inf-ImplementierenNRW-IF1BY-Inf-2

Das Array speichert Elemente in einem zusammenhängenden Speicherblock fester Größe. Der Indexzugriff ist daher O(1) (die Adresse wird direkt berechnet), aber Einfügen und Löschen in der Mitte kosten O(n), weil alle nachfolgenden Elemente verschoben werden müssen; in Java ist die Größe fest (`int[]`). Ein dynamisches Array (ArrayList) verdoppelt bei Bedarf seine Kapazität und erreicht so beim Anhängen amortisiert O(1).

Die einfach verkettete Liste besteht aus Knoten, die je einen Wert und einen Zeiger auf den Nachfolger halten. Einfügen und Löschen am Kopf sind O(1) (nur Zeiger umhängen), der Zugriff auf das k-te Element dagegen O(n), weil man von vorne durchhangeln muss. Anders als das Array liegt sie nicht zusammenhängend im Speicher und kann beliebig wachsen — der Preis ist der Zeiger-Overhead und ein schlechteres Cache-Verhalten.

Ein Stack (Stapel, LIFO — last in, first out) erlaubt Zugriff nur am oberen Ende über `push` (auflegen), `pop` (oberstes entnehmen) und `peek` (oberstes ansehen). Stapel modellieren den Methoden-Aufrufstapel, die Klammer- und Syntaxprüfung, die Rückgängig-Funktion und die Tiefensuche (DFS) — überall dort, wo das zuletzt Hinzugefügte zuerst bearbeitet wird.

Eine Queue (Warteschlange, FIFO — first in, first out) bedient am einen Ende mit `enqueue` (hinten anstellen) und am anderen mit `dequeue` (vorne entnehmen). Warteschlangen modellieren Druck- und Auftragspuffer, das Scheduling und die Breitensuche (BFS-Frontier). Eine Priority Queue verallgemeinert dies, indem stets das Element höchster Priorität entnommen wird (siehe Abschnitt Heaps).

Eine Deque (double-ended queue, meist doppelt verkettet) kombiniert beide Enden: Einfügen und Entnehmen sind an Kopf und Schwanz je O(1). Sie lässt sich sowohl als Stack als auch als Queue verwenden und ist damit die flexibelste lineare Struktur.

Skelett verkettete Liste: ```java class Knoten<T> { T wert; Knoten<T> next; } class Liste<T> { Knoten<T> kopf; void einfügenKopf(T x) { Knoten<T> n = new Knoten<>(); n.wert = x; n.next = kopf; kopf = n; } } ```

Typische Fehler

Stack und Queue verwechselt — LIFO (Stapel) vs. FIFO (Warteschlange).
Beim Löschen aus einer verketteten Liste den Vorgänger nicht angepasst — die Struktur wird inkonsistent.
`null`-Prüfung am Kopf vergessen — NullPointerException bei leerer Liste.
Array-Zugriff und verkettete Liste gleichgesetzt — die Liste hat keinen O(1)-Indexzugriff.

LK-Vertiefung

eA-Vertiefung: Implementieren Sie eine Queue mithilfe zweier Stacks (amortisiert O(1) je Operation) und begründen Sie die amortisierte Analyse über die Beobachtung, dass jedes Element höchstens einmal vom Eingangs- auf den Ausgangsstapel umgeschoben wird.

Aktive Wiederholung

Implementieren Sie eine generische Klasse `Stack<T>` mit verketteter Liste und beurteilen Sie die Laufzeit jeder Operation in O-Notation.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Bäume — Binärbäume, Suchbäume, Traversierungen#

StandardNRW-IF1BY-Inf-2BW-Inf-3

Binärer Suchbaum (BST) nach Einfügen 50, 30, 70, 20, 40, 60, 80

Abb. 1Linkes Kind kleiner als Vater, rechtes Kind größer. In-Order-Traversierung liefert die sortierte Folge 20 · 30 · 40 · 50 · 60 · 70 · 80.

Ein Baum ist eine hierarchische, rekursiv definierte Datenstruktur aus Knoten: Ein ausgezeichneter Knoten ist die Wurzel, jeder Knoten hat Kinder, Knoten ohne Kinder heißen Blätter. Bei einem Binärbaum hat jeder Knoten höchstens zwei Kinder (links, rechts). Die zentralen Maße: Die Tiefe eines Knotens ist sein Abstand zur Wurzel, die Höhe sein Abstand zum tiefsten Blatt; der Baum heißt vollständig, wenn alle Ebenen bis auf evtl. die letzte voll besetzt sind.

Der binäre Suchbaum (BST) erfüllt die Suchbaumeigenschaft: Im linken Teilbaum stehen nur kleinere, im rechten nur größere Schlüssel als im Knoten. Dadurch steigt man — wie bei der binären Suche — durch Vergleich nach links oder rechts ab; Suchen, Einfügen und Löschen kosten O(h) mit der Höhe h. Bei zufälliger Einfügereihenfolge ist h ≈ log n; bei sortierter Einfügung entartet der BST jedoch zur Liste mit h = n und damit O(n) je Operation.

Die vier Traversierungen durchlaufen alle Knoten in fester Ordnung: Preorder (Wurzel–Links–Rechts), Inorder (Links–Wurzel–Rechts), Postorder (Links–Rechts–Wurzel) und Levelorder (ebenenweise per Queue, also BFS). Besonders wichtig: Die Inorder-Traversierung eines BST liefert die Schlüssel in sortierter Reihenfolge — ein häufig geprüfter Standardfakt.

Code-Skelett BST: ```java Knoten suchen(Knoten n, int key) { if (n == null || n.wert == key) return n; return key < n.wert ? suchen(n.links, key) : suchen(n.rechts, key); } ```

Das Löschen im BST hat drei Fälle: ein Blatt (einfach entfernen), ein Knoten mit einem Kind (durch das Kind ersetzen) und ein Knoten mit zwei Kindern (durch den In-Order-Nachfolger ersetzen — den kleinsten Schlüssel des rechten Teilbaums). Um die Entartung zu verhindern, halten selbstbalancierende Bäume die Höhe in O(log n): AVL-Bäume über das strenge Balancekriterium |h_links − h_rechts| ≤ 1, Rot-Schwarz-Bäume über Färbungsregeln. Javas `TreeMap` und `TreeSet` nutzen Rot-Schwarz-Bäume.

Eine besondere Baumart ist der Heap — ein vollständiger Binärbaum mit Heap-Bedingung (Vater stets ≤ bzw. ≥ Kinder), Grundlage von Priority Queue und Heapsort (eigener Abschnitt). Bäume modellieren darüber hinaus Dateisysteme, die Syntaxbäume von Compilern, Entscheidungsbäume und die Indexstrukturen von Datenbanken (B-Bäume).

Musterlösung

Binären Suchbaum aufbauen und Suchpfad analysieren

Fügen Sie der Reihe nach 50, 30, 70, 20, 40, 60, 80 in einen anfangs leeren BST ein. Geben Sie In-Order- und Pre-Order-Traversierung sowie die Suchpfadlänge für 60 an.

Schritt 1 — Wurzel und obere Ebene
50 wird Wurzel; 30 < 50 → links, 70 > 50 → rechts.
Schritt 2 — Zweite Ebene
20 < 30 → links unter 30; 40 > 30 → rechts unter 30; 60 < 70 → links unter 70; 80 > 70 → rechts unter 70.
Schritt 3 — Traversierungen
In-Order: 20 30 40 50 60 70 80 (sortiert!). Pre-Order: 50 30 20 40 70 60 80.
Schritt 4 — Suchpfad für 60
50 → 70 → 60 — drei Vergleiche, Pfadlänge 2. Höhe des Baums h = 2; Suche im balancierten BST in O(log n).

Ergebnis: In-Order liefert sortierte Folge; Suche nach 60 benötigt 3 Vergleiche.

Typische Fehler

BST mit Heap verwechselt — die Heap-Bedingung ordnet vertikal (Vater/Kind), die BST-Bedingung horizontal (links < Knoten < rechts).
Beim Löschen eines BST-Knotens mit zwei Kindern den In-Order-Nachfolger nicht korrekt eingesetzt.
Höhe und Tiefe vertauscht.
Entartung des unbalancierten BST übersehen — O(log n) gilt nur bei (annähernd) balancierter Höhe.

LK-Vertiefung

eA-Vertiefung: Begründen Sie qualitativ, warum die Höhe eines AVL-Baums mit n Knoten in O(log n) liegt (Balancekriterium |h_l − h_r| ≤ 1).

Aktive Wiederholung

Implementieren Sie die Inorder-Traversierung eines Binärbaums rekursiv und iterativ; vergleichen Sie Speicher- und Laufzeitverhalten.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Graphen — Modell, Repräsentation, BFS, DFS, Dijkstra#

StandardNRW-IF1BY-Inf-2BW-Inf-3

Gewichteter Graph für Dijkstra — kürzester Weg A → E

Abb. 2Kantengewichte als Distanzen; Dijkstras Algorithmus liefert hier A → B → C → E mit Länge 6.

Ein Graph G = (V, E) besteht aus einer Knotenmenge V und einer Kantenmenge E ⊆ V × V. Man unterscheidet gerichtete (Kanten haben eine Richtung) von ungerichteten, gewichtete (Kanten tragen Zahlen, z. B. Entfernungen) von ungewichteten sowie zyklische von azyklischen Graphen. Graphen sind das allgemeinste Modell für Beziehungen zwischen Objekten und verallgemeinern Bäume (ein Baum ist ein zusammenhängender, kreisfreier Graph).

Zwei Standard-Repräsentationen stehen zur Wahl: Die Adjazenzmatrix ist eine |V|×|V|-Tabelle mit einem Eintrag je möglicher Kante — sie prüft eine Kante in O(1), braucht aber O(|V|²) Speicher und lohnt bei dichten Graphen. Die Adjazenzliste speichert je Knoten die Liste seiner Nachbarn — sie ist O(|V| + |E|) sparsam und damit für dünne Graphen die Regel. Bei gerichteten Graphen ist die Matrix nicht symmetrisch.

Die Breitensuche (BFS) erkundet den Graphen schichtweise mit einer FIFO-Queue: Sie besucht zuerst alle direkten Nachbarn, dann deren Nachbarn usw. In einem ungewichteten Graphen findet sie damit die kürzesten Pfade (gemessen in Kantenzahl); Laufzeit auf einer Adjazenzliste O(|V| + |E|). Eine „Besucht"-Markierung verhindert Mehrfachbesuche und Endlosschleifen in zyklischen Graphen.

Die Tiefensuche (DFS) folgt jedem Pfad so weit wie möglich, bevor sie zurücksetzt — realisiert über Rekursion oder einen expliziten Stack. Sie erzeugt einen Spannbaum, klassifiziert Kanten (Baum-, Rück-, Vorwärts-, Querkante) und ist die Grundlage für topologisches Sortieren, Zyklenerkennung und das Finden von Zusammenhangskomponenten — ebenfalls O(|V| + |E|).

Für kürzeste Pfade in gewichteten Graphen mit nicht-negativen Kanten liefert der Dijkstra-Algorithmus das Ergebnis: ein Greedy-Verfahren (Querverweis Algorithmen), das wiederholt den noch nicht abgeschlossenen Knoten kleinster bekannter Distanz wählt und dessen Nachbarn aktualisiert (Kanten-Relaxation). Mit einer Priority Queue (Heap, siehe nächster Abschnitt) erreicht er O((|V| + |E|) log |V|). Bei negativen Kantengewichten versagt Dijkstra — dann ist Bellman-Ford zu verwenden.

Graphen modellieren Routen- und Navigationsnetze (Dijkstra, A*), soziale Netzwerke, Abhängigkeitsgraphen in Compilern und Build-Systemen sowie das Web (Webcrawler, PageRank) — eine der universellsten Strukturen der Informatik.

Musterlösung

BFS und DFS auf einem Beispielgraphen

Geben Sie die BFS- und DFS-Reihenfolge ausgehend von Knoten A im Graphen mit Kanten {A-B, A-C, B-D, B-E, C-F} an.

Schritt 1 — Datenstrukturen wählen
BFS verwendet eine FIFO-Queue, DFS einen LIFO-Stack (bzw. Rekursion).
Schritt 2 — BFS Ablauf
Queue: [A] → besuche A, Queue: [B,C] → besuche B, Queue: [C,D,E] → C → D → E → F. Reihenfolge: A, B, C, D, E, F.
Schritt 3 — DFS rekursiv ab A
A → B → D (zurück) → E (zurück, zurück) → C → F. Reihenfolge: A, B, D, E, C, F.
Schritt 4 — Komplexität
Beide Verfahren laufen in O(V + E) auf Adjazenzlisten. BFS findet kürzeste Pfade in ungewichteten Graphen, DFS eignet sich für Topologische Sortierung.

Ergebnis: BFS: A, B, C, D, E, F. DFS: A, B, D, E, C, F.

Typische Fehler

BFS auf gewichteten Graphen für kürzeste Pfade gehalten — dafür ist Dijkstra zuständig.
Bei DFS die „Besucht"-Markierung vergessen — Endlosschleife in zyklischen Graphen.
Adjazenzmatrix eines gerichteten Graphen fälschlich symmetrisch eingetragen.
Dijkstra auf Graphen mit negativen Kanten angewandt — das Greedy-Argument trägt dort nicht.

LK-Vertiefung

eA-Vertiefung: Modifizieren Sie Dijkstra so, dass er nicht nur die Distanz, sondern auch den Pfad rekonstruiert (Vorgänger-Array).

Aktive Wiederholung

Implementieren Sie BFS auf einer Adjazenzliste und ermitteln Sie die kürzeste Pfadlänge zwischen zwei Knoten; analysieren Sie die Laufzeit in O-Notation.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Hashtabellen, Kollisionsbehandlung und Lastfaktor#

VertiefungNRW-IF1BY-Inf-2

Hashtabelle mit Verkettung (Chaining)

Abb. 3Bucket-Array der Größe 7; Kollisionen lösen sich über verkettete Listen je Slot. h(Anna) = h(Anton) = 1 (Kollision), h(Ben) = 3, h(Carla) = h(Cäsar) = h(Christof) = 5; Lastfaktor α = n/m.

Eine Hashtabelle speichert Schlüssel-Wert-Paare in einem Bucket-Array und erreicht im Mittel O(1) für Einfügen, Suchen und Löschen — schneller als jede vergleichsbasierte Struktur. Kern ist die Hashfunktion, die einen Schlüssel auf einen Bucket-Index abbildet (typisch h(k) = k.hashCode() mod m). Eine gute Hashfunktion streut gleichmäßig über alle Buckets, ist schnell berechenbar und deterministisch.

Da viele Schlüssel auf denselben Index fallen können, sind Kollisionen unvermeidlich (vgl. das Geburtstagsparadoxon) und müssen behandelt werden. Beim Separate Chaining trägt jeder Bucket eine verkettete Liste (oder einen Baum) kollidierender Einträge. Beim Open Addressing wird bei Kollision nach fester Regel ein anderer freier Bucket gesucht — lineares Sondieren (nächster Slot), quadratisches Sondieren oder Double Hashing (eine zweite Hashfunktion bestimmt die Schrittweite).

Der Lastfaktor α = n/m (n Einträge, m Buckets) misst die Füllung. Mit steigendem α wachsen die Kollisionsketten und damit die Zugriffszeit; überschreitet α eine Schwelle (oft 0,75), wird rehasht: ein größeres Array (meist doppelt so groß) wird angelegt und alle Einträge neu eingefügt. Ein einzelnes Rehashing kostet O(n), über viele put-Operationen verteilt aber nur O(1) amortisiert.

Die durchschnittliche Laufzeit ist O(1), der Worst Case jedoch O(n) — wenn alle Schlüssel auf denselben Bucket fallen (degenerierte Kette). Genau das macht Hashtabellen anfällig für Hash-Flooding-Angriffe (DoS) mit absichtlich kollidierenden Schlüsseln. Javas `HashMap` wandelt eine Bucket-Liste deshalb seit Java 8 ab acht Einträgen in einen Rot-Schwarz-Baum um und begrenzt den Worst Case so auf O(log n).

In Java gilt ein Vertrag zwischen `hashCode()` und `equals()`: Gleiche Objekte (`equals` liefert true) müssen denselben Hashcode liefern. Wer `equals` überschreibt, ohne `hashCode` anzupassen, bricht diesen Vertrag — die Objekte landen in verschiedenen Buckets und werden in `HashSet`/`HashMap` nicht mehr gefunden.

Hashtabellen sind die Standardimplementierung von Mengen (`HashSet`) und Abbildungen (`HashMap`/dict), von Caches, der Deduplizierung und von Datenbank-Hash-Indizes. Beim Open Addressing erfordert das Löschen eine Tombstone-Markierung (logisch gelöscht), damit nachfolgende Sondierketten nicht abreißen — andernfalls entstehen falsche „nicht gefunden"-Ergebnisse.

\alpha = \frac{n}{m}

Lastfaktor einer Hashtabelle

n Elemente, m Buckets; α > 0,75 begünstigt Rehashing bei Open Addressing.

Typische Fehler

`hashCode()` ohne `equals()` (oder umgekehrt) überschrieben — verletzt den Java-Hashtabellen-Vertrag.
Lastfaktor mit der Anzahl der Kollisionen verwechselt.
Beim linearen Sondieren das gelöschte Element nicht als Tombstone markiert — nachfolgende Suchen liefern falsche Negative.
Average-Case O(1) als Garantie gelesen — bei vielen Kollisionen droht O(n).

LK-Vertiefung

eA-Vertiefung: Konstruieren Sie eine bewusst kollidierende Eingabesequenz für eine modulo-basierte Hashfunktion und beurteilen Sie die Sicherheitsfolgen.

Aktive Wiederholung

Implementieren Sie eine Hashtabelle mit Separate Chaining und Lastfaktor-getriebenem Rehashing; analysieren Sie die amortisierte Laufzeit für `put`.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Abstrakte Datentypen, Schnittstellen und generische Programmierung#

BasisKMK-EPA-Inf-ModellierenNRW-IF1BY-Inf-2

UML-Klassendiagramm — Vererbung Tier → Hund

Abb. 4Tier (abstrakt) wird von Hund spezialisiert; offene Pfeilspitze zeigt zur Oberklasse, Bezeichner kursiv für abstrakte Methoden.

Ein abstrakter Datentyp (ADT) definiert eine Menge von Werten zusammen mit den darauf erlaubten Operationen und deren Verhalten — ohne die Implementation festzulegen. Er trennt das Was (die Spezifikation der Schnittstelle: welche Operationen, mit welchen Vor- und Nachbedingungen) vom Wie (der konkreten Realisierung). Diese Trennung ist die datenstrukturelle Entsprechung der Kapselung und das Leitprinzip dieses Topics.

Der ADT Stack etwa ist allein durch seine Operationen `push(x)`, `pop()`, `peek()` und `isEmpty()` samt LIFO-Verhalten definiert. Ob darunter ein Array oder eine verkettete Liste liegt, ist für die Nutzerin unsichtbar — beide erfüllen denselben Vertrag, unterscheiden sich aber in Laufzeit und Speicher. Genau das erlaubt es, die Implementierung später auszutauschen, ohne den nutzenden Code zu ändern.

In Java realisiert ein Interface den ADT-Vertrag formal: Es deklariert die Operationssignaturen, konkrete Klassen implementieren sie. In Python genügt ein Protokoll — eine Klasse, die die erwarteten Methoden bereitstellt, erfüllt den ADT implizit („Duck Typing": Wenn es wie eine Ente quakt, ist es eine Ente). So wird der ADT vom Konzept zum überprüfbaren Typ.

Mit generischen Typen (Java `<T>`, Python-Type-Hints) werden Container typsicher und wiederverwendbar, ohne unsichere Typumwandlungen (Casts): `Stack<String>` und `Stack<Integer>` teilen denselben Code, garantieren aber je den richtigen Elementtyp bereits zur Compile-Zeit. Generizität parametrisiert über Typen und ist klar von der Vererbung zu unterscheiden, die Verhalten spezialisiert.

Die Vorteile der ADT-Sicht sind eine austauschbare Implementierung, lokal begrenzte Änderungen, klar prüfbare Invarianten sowie bessere Wiederverwendung und Testbarkeit. Programmiert man „gegen die Schnittstelle, nicht gegen die Implementierung", bleiben Systeme flexibel — ein Kernprinzip der Softwaretechnik.

Die Wahl der zugrunde liegenden Struktur richtet sich nach dem dominanten Zugriffsmuster: wahlfreier Indexzugriff → Array; häufiges Einfügen/Löschen am Anfang → verkettete Liste; schnelles Minimum/Maximum → Heap; schnelle Existenzprüfung → Hashtabelle. Derselbe ADT wird je nach Bedarf anders realisiert.

ADT-Skelett: ```java interface Stapel<T> { void push(T x); T pop(); boolean isEmpty(); } ```

Typische Fehler

ADT mit einer konkreten Datenstruktur gleichgesetzt — der ADT ist implementierungsfrei.
Generische Typen mit Vererbung verwechselt — Generizität parametrisiert über Typen, Vererbung spezialisiert Verhalten.
Invarianten des ADT durch direkten Feldzugriff verletzt, weil die Kapselung umgangen wurde.
Den ADT durch Implementierungscode statt durch Operationssignaturen „spezifiziert".

LK-Vertiefung

eA-Vertiefung: Spezifizieren Sie den ADT „Warteschlange" formal über Vor- und Nachbedingungen seiner Operationen und beurteilen Sie, warum ein Ringpuffer-Array gegenüber der verketteten Liste Speicher spart, aber eine feste Kapazität bzw. ein Vergrößern (Rehashing/Umkopieren) erfordert.

Aktive Wiederholung

Modellieren Sie den ADT „Warteschlange" durch seine Operationen und implementieren Sie ihn generisch sowohl mit einem Ringpuffer-Array als auch mit einer verketteten Liste; beurteilen Sie die jeweiligen Laufzeiten.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Heaps, Priority Queues und Heapsort#

VertiefungNRW-IF1BY-Inf-2BW-Inf-3

Min-Heap nach Einfügen von 5, 3, 8, 1, 9, 2

Abb. 5Heap-Bedingung (vertikal): jeder Knoten ≤ seine Kinder. Speicherung im Array [1, 3, 2, 5, 9, 8]: linkes Kind 2i+1, rechtes Kind 2i+2.

Ein Binär-Heap ist ein vollständiger Binärbaum (alle Ebenen bis auf die letzte voll, die letzte von links gefüllt), der die Heap-Bedingung erfüllt: Im Min-Heap ist jeder Knoten ≤ seine Kinder (das Minimum steht an der Wurzel), im Max-Heap ≥. Die Bedingung ordnet vertikal (Vater/Kind) und ist damit deutlich schwächer als die BST-Bedingung — Geschwister sind untereinander nicht geordnet.

Dank der Vollständigkeit speichert man den Heap ohne Zeiger in einem Array: Für den Knoten mit Index i liegt das linke Kind bei 2i+1, das rechte bei 2i+2 und der Vater bei ⌊(i−1)/2⌋ (0-basiert). Diese implizite Adressierung spart Speicher und ist cache-freundlich — gerade dadurch ist der Heap so effizient.

Der Heap ist die Standard-Implementierung der Priority Queue — eines ADT, der stets das Element höchster (bzw. niedrigster) Priorität liefert, nicht das zuerst eingefügte (anders als die FIFO-Queue). Einfügen und Entnehmen kosten je O(log n), das Minimum (bzw. Maximum) ablesen O(1).

Zwei Operationen erhalten die Heap-Bedingung: Beim insert wird das Element ans Array-Ende gehängt und steigt per sift-up (Aufsteigen) auf, solange es kleiner als sein Vater ist. Beim extractMin/Max wird die Wurzel entnommen, das letzte Element an die Spitze gesetzt und per sift-down (Absinken) mit dem jeweils kleineren bzw. größeren Kind getauscht, bis die Bedingung wieder gilt. Beide Pfade sind höchstens so lang wie die Baumhöhe ⌊log n⌋ → O(log n).

Der Heapsort baut aus dem Array zunächst einen Max-Heap (bottom-up per Floyd-Heapify in O(n)) und tauscht dann wiederholt die Wurzel (das Maximum) ans Ende, verkleinert den Heap und stellt ihn per sift-down wieder her. Gesamtlaufzeit O(n log n), in-place (kein Zusatzspeicher), aber nicht stabil.

Heaps liefern die Priority Queue für Dijkstra/A, treiben Ereignissimulationen und Task-Scheduler, lösen die Top-k-Auswahl und erlauben über zwei gegenläufige Heaps ein Median-Streaming. Java stellt `PriorityQueue<E>` bereit — standardmäßig ein Min-Heap* über die natürliche Ordnung oder einen `Comparator`.

Musterlösung

Min-Heap aufbauen (sift-up) und extractMin (sift-down)

Fügen Sie 5, 3, 8, 1, 9, 2 nacheinander in einen anfangs leeren Min-Heap ein und führen Sie anschließend ein extractMin durch. Geben Sie jeweils die Array-Darstellung an.

Schritt 1 — Einfügen mit sift-up
Jedes Element wird ans Array-Ende gehängt und steigt auf, solange es kleiner als sein Vater ist. 5 → [5]; 3 → [3,5] (3 < 5, getauscht); 8 → [3,5,8]; 1 → [1,3,8,5] (1 steigt über 5 und 3 auf); 9 → [1,3,8,5,9].
Schritt 2 — Letztes Element 2 einfügen
2 ans Ende: [1,3,8,5,9,2] (Index 5). Der Vater liegt bei ⌊(5−1)/2⌋ = 2, dort steht 8; wegen 2 < 8 tauschen: [1,3,2,5,9,8]. Neuer Vater bei Index 0 ist 1; 2 > 1 → Abbruch. Heap: [1,3,2,5,9,8].
Schritt 3 — extractMin: Wurzel entnehmen
Das Minimum 1 (Wurzel) wird zurückgegeben. Das letzte Element 8 rückt an die Spitze: [8,3,2,5,9]. Nun muss 8 wieder absinken (sift-down).
Schritt 4 — sift-down und Aufwand
Die Kinder von 8 (Index 0) sind 3 (Index 1) und 2 (Index 2); das kleinste Kind ist 2 → tauschen: [2,3,8,5,9]. 8 steht jetzt auf Index 2 ohne Kinder → fertig. Sowohl insert als auch extractMin laufen in O(log n), da der zurückgelegte Pfad höchstens so lang wie die Baumhöhe ist.

Ergebnis: Heap nach Aufbau: [1,3,2,5,9,8]; nach extractMin zurückgegeben 1, Heap [2,3,8,5,9]. Jede Operation in O(log n).

Typische Fehler

Heap-Bedingung mit BST-Bedingung verwechselt — der Heap ordnet vertikal (Vater/Kind), nicht horizontal (links/rechts).
Array-Indizierung verschoben (1-basiert vs. 0-basiert) — falsche Vater-/Kind-Indizes.
Heapsort als stabil bezeichnet — er ist nicht stabil.
sift-down beim extractMin vergessen — der Heap bleibt verletzt.

LK-Vertiefung

eA-Vertiefung: Beweisen Sie, dass der bottom-up-Heapaufbau (Floyd) in O(n) liegt, indem Sie die Summe der Sift-down-Kosten über alle Ebenen abschätzen.

Aktive Wiederholung

Fügen Sie die Werte 5, 3, 8, 1, 9, 2 nacheinander in einen anfangs leeren Min-Heap ein, stellen Sie den Heap als Array dar und analysieren Sie die Laufzeit einer extractMin-Operation.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Datenstrukturen — Listen, Stacks, Queues, Bäume, Graphen, Hashtabellen

6Abschnitteca. 19Min Lesezeit3KompetenzenNiveauBasis 2 · Standard 2 · Vertiefung 2Stand 06/2026