Heaps und Priority Queues in C++: Eine praktische Einführung für NIU CSCI 340

Einführung in Heaps und Priority Queues

In der NIU CSCI 340 Assignment 9 geht es um die Implementierung von binären Heaps und einer darauf basierenden Priority Queue. Heaps sind eine spezielle Baumstruktur, die es erlaubt, das „beste“ Element nach einem bestimmten Kriterium schnell zu finden – ähnlich wie bei einer Leaderboard-Aktualisierung in einem Online-Spiel, wo der Spieler mit der höchsten Punktzahl immer oben steht. In diesem Tutorial lernst du die wichtigsten Funktionen kennen und wie du sie in C++ umsetzt.

Grundlagen: Binärer Heap als Array

Ein binärer Heap wird als vollständiger Binärbaum dargestellt, der von links nach rechts gefüllt ist. Statt Zeigern wird ein Array verwendet, wobei die Wurzel bei Index 0 liegt. Für einen Knoten an Index i gilt:

• Linkes Kind: heap_left(i) = 2*i + 1
• Rechtes Kind: heap_right(i) = 2*i + 2
• Elternknoten: heap_parent(i) = (i-1)/2 (für i>0, sonst 0)

Diese Indexberechnungen sind essenziell für alle weiteren Heap-Operationen. Ein Beispiel: Bei einem Array der Größe 10 liegen die Knoten in Level-Order vor: Index 0 ist die Wurzel, Index 1 und 2 sind die Kinder, usw.

Heap-Eigenschaft und Vergleichsfunktionen

Es gibt Min-Heaps (kleinere Werte oben) und Max-Heaps (größere Werte oben). Die Vergleichsfunktion compare(parent, child) gibt true zurück, wenn die Heap-Eigenschaft erfüllt ist. Für einen Min-Heap verwendet man std::less (parent < child), für einen Max-Heap std::greater (parent > child).

Die Funktion is_heap(heapdata, nodes, compare) prüft, ob für jeden Knoten die Heap-Eigenschaft gilt. Das ist nützlich, um nach Einfügungen oder Extraktionen die Korrektheit zu testen.

Traversierung: Preorder, Inorder, Postorder, Levelorder

Obwohl Heaps normalerweise nicht traversiert werden, verlangt die Aufgabe die Implementierung von Traversierungsfunktionen für den zugrunde liegenden Binärbaum:

• heap_preorder: Besuche Wurzel, dann linkes Kind, dann rechtes Kind.
• heap_inorder: Besuche linkes Kind, dann Wurzel, dann rechtes Kind.
• heap_postorder: Besuche linkes Kind, dann rechtes Kind, dann Wurzel.
• heap_levelorder: Besuche Knoten Ebene für Ebene von links nach rechts.

Diese Funktionen nehmen den Heap-Array, die Knotenanzahl, den Startindex und eine Besucherfunktion entgegen. Zum Beispiel für heap_preorder:

void heap_preorder(const vector<int>& heapdata, size_t nodes, size_t node, function<void(int)> fn) {
    if (node >= nodes) return;
    fn(heapdata[node]);
    heap_preorder(heapdata, nodes, heap_left(node), fn);
    heap_preorder(heapdata, nodes, heap_right(node), fn);
}

Bubble-Up und Bubble-Down – Die Kernoperationen

Beim Bubble-Up (auch „percolate up“) wird ein neu eingefügter Knoten solange mit seinem Elternknoten getauscht, bis die Heap-Eigenschaft wiederhergestellt ist. Die Funktion heap_bubble_up(begin, nodes, start, compare) beginnt am Index start und tauscht mit dem Elternknoten, wenn die Vergleichsfunktion false liefert. Sie gibt die Anzahl der Vertauschungen zurück.

Beim Bubble-Down („percolate down“) wird ein Knoten (z.B. die neue Wurzel nach einer Extraktion) solange mit dem größeren/kleineren Kind getauscht, bis die Heap-Eigenschaft gilt. Die Funktion heap_bubble_down(begin, nodes, start, compare) arbeitet analog.

Ein Beispiel für Bubble-Down in einem Min-Heap:

size_t heap_bubble_down(vector<int>& heap, size_t nodes, size_t start, function<bool(int,int)> compare) {
    size_t swaps = 0;
    size_t i = start;
    while (true) {
        size_t left = heap_left(i);
        size_t right = heap_right(i);
        size_t smallest = i;
        if (left < nodes && !compare(heap[smallest], heap[left])) smallest = left;
        if (right < nodes && !compare(heap[smallest], heap[right])) smallest = right;
        if (smallest != i) {
            swap(heap[i], heap[smallest]);
            swaps++;
            i = smallest;
        } else break;
    }
    return swaps;
}

Einfügen und Extrahieren

Die Funktion heap_insert(heapdata, nodes, key, compare) fügt einen neuen Schlüssel am Ende des Arrays ein und führt dann heap_bubble_up aus. Die Variable nodes wird per Referenz übergeben und muss inkrementiert werden.

Die Funktion heap_extract(heapdata, nodes, compare) entfernt die Wurzel (das höchstpriore Element), ersetzt sie durch das letzte Element, dekrementiert nodes und führt heap_bubble_down aus. Der extrahierte Wert wird zurückgegeben.

Heapify und Heapsort

Mit heapify_in_place_up und heapify_in_place_down kann man ein unsortiertes Array in einen Heap umwandeln. Die Variante von oben („up“) fügt nacheinander Elemente ein, während die Variante von unten („down“) effizienter ist und in O(n) arbeitet.

Heap-Sort nutzt die Heap-Eigenschaft: Man erstellt einen Max-Heap und extrahiert dann wiederholt die Wurzel, wodurch die Elemente absteigend sortiert werden. Die Funktion heap_sort implementiert dieses Verfahren.

Priority-Queue-Klasse

Die Klasse heap_priority_queue kapselt den Heap und bietet eine Standard-Schnittstelle:

• Konstruktor: heap_priority_queue(ITERATOR first, ITERATOR last) erstellt einen Heap aus dem Iteratorbereich.
• top(): Gibt das oberste Element zurück (ohne es zu entfernen).
• empty(): Prüft, ob die Queue leer ist.
• size(): Gibt die Anzahl der Elemente zurück.
• push(key): Fügt ein Element ein.
• pop(): Entfernt das oberste Element.

Die Implementierung nutzt intern die Heap-Funktionen. Ein Beispiel für die Klasse:

template <typename T, typename Container = vector<T>, typename Compare = less<T>>
class heap_priority_queue {
private:
    Container data;
    Compare comp;
public:
    heap_priority_queue() {}
    template <typename InputIt>
    heap_priority_queue(InputIt first, InputIt last) : data(first, last) {
        heapify_in_place_down(data, data.size(), comp);
    }
    const T& top() const { return data.front(); }
    bool empty() const { return data.empty(); }
    size_t size() const { return data.size(); }
    void push(const T& key) {
        heap_insert(data, data.size(), key, comp);
    }
    void pop() {
        heap_extract(data, data.size(), comp);
    }
};

Praktische Tipps und häufige Fehler

Beachte die Indexgrenzen: Bei der Berechnung von Kind- und Elternindizes darfst du nicht über die Array-Grenzen hinausgreifen, besonders bei heap_left und heap_right. Die Traversierungsfunktionen müssen rekursiv oder iterativ arbeiten – achte darauf, dass der node-Parameter gültig ist.

Ein häufiger Fehler ist das Vergessen, nodes per Referenz zu aktualisieren. In heap_insert muss nodes nach dem Einfügen inkrementiert werden, sonst stimmt die Größe nicht.

Teste deine Implementierung mit verschiedenen Vergleichsfunktionen (Min-Heap vs. Max-Heap) und mit leeren Heaps. Verwende is_heap, um nach jeder Operation die Korrektheit zu prüfen.

Trend-Beispiel: Gaming-Leaderboard mit Priority Queue

Stell dir vor, du entwickelst ein Online-Game, in dem die Spieler nach ihrem Score in einer Rangliste sortiert werden. Jedes Mal, wenn ein Spieler einen neuen Highscore erzielt, muss dieser in die Rangliste eingefügt werden – das entspricht heap_insert. Der Spieler mit dem höchsten Score steht immer oben (Max-Heap). Mit top() zeigst du den aktuellen Leader an, und mit pop() entfernst du ihn, wenn er nicht mehr im Rennen ist. So bleibt die Rangliste stets aktuell, ohne dass du jedes Mal neu sortieren musst – ein klassischer Anwendungsfall für Priority Queues.

Zusammenfassung

In diesem Tutorial hast du gelernt, wie man einen binären Heap in C++ implementiert, inklusive der wichtigsten Operationen wie Bubble-Up, Bubble-Down, Einfügen, Extrahieren und Traversieren. Du hast auch gesehen, wie man eine Priority-Queue-Klasse baut, die auf dem Heap basiert. Mit diesen Kenntnissen bist du bestens gerüstet, um die NIU CSCI 340 Assignment 9 zu lösen. Viel Erfolg!