Informatik Datenstrukturen – Heaps und Prioritätswarteschlangen
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was ist ein Heap? · Worin unterscheiden sich Min-Heap und Max-Heap?
Karten
15 KartenWas ist ein Heap?
Rückseite
Ein Heap ist ein fast vollständiger binärer Baum, der die Heap-Eigenschaft erfüllt: Jeder Knoten ist größer (Max-Heap) oder kleiner (Min-Heap) als seine Kinder.
Worin unterscheiden sich Min-Heap und Max-Heap?
Rückseite
Im Min-Heap ist der Wurzelknoten das Minimum (Elternteil ≤ Kinder), im Max-Heap das Maximum (Elternteil ≥ Kinder).
Wie wird ein binärer Heap im Array gespeichert?
Rückseite
Levelorder im Array ab Index 0: Kinder von Index i liegen bei 2i+1 und 2i+2, Elternteil bei floor((i-1)/2).
Was bedeutet die Heap-Eigenschaft formal?
Rückseite
Für alle Knoten i außer der Wurzel gilt: key[parent(i)] ≥ key[i] (Max-Heap) bzw. ≤ (Min-Heap).
Wie funktioniert das Heapify-Verfahren (Sift-Down)?
Rückseite
Vergleiche Knoten mit seinen Kindern, tausche mit dem größeren (Max-Heap) oder kleineren (Min-Heap) Kind und wiederhole rekursiv nach unten.
Wie läuft das Einfügen (Insert) in einen Heap ab?
Rückseite
Neues Element am Array-Ende anhängen, dann per Sift-Up (Bubbling) mit Elternteil vergleichen und tauschen, bis Heap-Eigenschaft wiederhergestellt ist.
Wie wird das Maximum/Minimum aus einem Heap entfernt (Extract-Max/Min)?
Rückseite
Wurzel mit letztem Element vertauschen, letztes Element entfernen, dann Heapify an der Wurzel ausführen.
Warum läuft Build-Heap in O(n) und nicht O(n log n)?
Rückseite
Nur O(n/2) Knoten sind keine Blätter; die Summe der Höhen aller Knoten ist linear, nicht n·log n.
Welche Zeitkomplexitäten haben die Heap-Operationen?
Rückseite
Insert: O(log n), Extract-Max/Min: O(log n), Heapify: O(log n), Build-Heap: O(n), Peek: O(1).
Was ist eine Prioritätswarteschlange (Priority Queue) als abstrakter Datentyp?
Rückseite
Eine Sammlung mit Operationen Insert, Extract-Max/Min, Peek – Elemente haben Priorität, höchste wird zuerst entnommen.
Wie implementiert man eine Priority Queue effizient?
Rückseite
Mit einem binären Heap: Insert und Extract-Max/Min in O(log n), Peek in O(1), Speicherplatz O(n).
Welche Rolle spielen Heaps beim Heapsort?
Rückseite
Build-Heap in O(n), dann n-mal Extract-Max und am Array-Ende ablegen – in-place Sortierung in O(n log n) Worst-Case.
Warum nutzen Dijkstra und Prim Heaps / Priority Queues?
Rückseite
Beide Algorithmen benötigen wiederholt das Minimum unbesuchter Knoten (Extract-Min) und Prioritätsaktualisierungen (Decrease-Key) – Heaps machen dies in O(log n).
Was leistet die Decrease-Key-Operation in einem Heap?
Rückseite
Verringert den Schlüsselwert eines Knotens und stellt per Sift-Up die Heap-Eigenschaft wieder her – wichtig für Dijkstra mit Priority Queue.
Welchen Vorteil bietet die Array-Darstellung gegenüber Zeigerbäumen?
Rückseite
Kein Speicher-Overhead für Zeiger, bessere Cache-Lokalität durch kontiguen Speicher, einfache Index-Arithmetik für Navigation.