Implementierung von Min Heap mit Prioritätswarteschlange

Einführung

In diesem Lab werden wir lernen, wie man eine Min Heap mit einer Prioritätswarteschlange in C++ implementiert. Wir werden ein C++-Programm implementieren, das grundlegende Operationen auf einer Min Heap ausführen kann.

Erstellen eines neuen C++-Programms

Erstellen Sie ein neues C++-Programm im Verzeichnis ~/project, indem Sie die folgenden Befehle in der Konsole ausführen:

cd ~/project
touch main.cpp

Fügen Sie die erforderlichen Headerdateien hinzu

Wir beginnen, indem wir die erforderlichen Headerdateien in unserem Programm einfügen:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

Definieren Sie die show()-Funktion

Als nächstes definieren wir eine Funktion, die die Elemente der Min Heap ausgibt. Diese Funktion nimmt eine Prioritätswarteschlange als Argument entgegen und verwendet eine Kopie der Prioritätswarteschlange, um die ursprüngliche Prioritätswarteschlange zu erhalten.

// Funktion zum Ausgeben der Elemente der Min Heap
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Kopieren der Prioritätswarteschlange in eine andere, um die ursprüngliche Prioritätswarteschlange zu erhalten
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Ausgabe des obersten Elements
        mh.pop();                 // Löschen des obersten Elements, um zum nächsten zu gelangen
    }

    cout << endl;
}

Implementieren Sie die main()-Funktion

In der main()-Funktion werden wir eine Prioritätswarteschlange von ganzen Zahlen erstellen und sie mit Elementen füllen.

int main()
{
    // Erstellen einer Prioritätswarteschlange von ganzen Zahlen
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Füllen der Prioritätswarteschlange mit Elementen
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Ausgeben der Anzahl der Elemente in der Min Heap
    cout << "Die Anzahl der Elemente in der Min Heap beträgt: " << minHeap.size() << endl;

    // Ausgeben des ersten Elements oder des Elements mit der höchsten Priorität
    cout << "Das erste Element oder das Element mit der höchsten Priorität ist: " << minHeap.top() << endl;

    // Ausgeben der Elemente der Min Heap
    cout << "Die Elemente der Min Heap sind: ";
    show(minHeap);

    // Löschen des ersten oder des kleinsten Elements aus der Min Heap
    minHeap.pop();

    // Ausgeben der Min Heap nach dem Löschen des kleinsten Elements
    cout << "Nachdem das erste oder das kleinste Element aus der Min Heap gelöscht wurde, wird es zu: ";
    show(minHeap);

    // Ausgeben der Anzahl der Elemente in der Min Heap nach dem Löschen des kleinsten Elements
    cout << "Die Anzahl der Elemente in der Min Heap nach dem Löschen des kleinsten Elements beträgt: " << minHeap.size() << endl;

    return 0;
}

Kompilieren und Ausführen des Programms

Um das Programm zu kompilieren, führen Sie im Terminal folgenden Befehl aus:

g++ main.cpp -o main

Dieser Befehl kompiliert den Quellcode main.cpp und erstellt eine ausführbare Datei namens main.

Um das Programm auszuführen, führen Sie folgenden Befehl aus:

./main

Vollständiger Code von main.cpp

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Funktion zum Ausgeben der Elemente der Min Heap
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Kopieren der Prioritätswarteschlange in eine andere, um die ursprüngliche Prioritätswarteschlange zu erhalten
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Ausgabe des obersten Elements
        mh.pop();                 // Löschen des obersten Elements, um zum nächsten zu gelangen
    }

    cout << endl;
}

int main()
{
    // Erstellen einer Prioritätswarteschlange von ganzen Zahlen
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Füllen der Prioritätswarteschlange mit Elementen
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Ausgeben der Anzahl der Elemente in der Min Heap
    cout << "Die Anzahl der Elemente in der Min Heap beträgt: " << minHeap.size() << endl;

    // Ausgeben des ersten Elements oder des Elements mit der höchsten Priorität
    cout << "Das erste Element oder das Element mit der höchsten Priorität ist: " << minHeap.top() << endl;

    // Ausgeben der Elemente der Min Heap
    cout << "Die Elemente der Min Heap sind: ";
    show(minHeap);

    // Löschen des ersten oder des kleinsten Elements aus der Min Heap
    minHeap.pop();

    // Ausgeben der Min Heap nach dem Löschen des kleinsten Elements
    cout << "Nachdem das erste oder das kleinste Element aus der Min Heap gelöscht wurde, wird es zu: ";
    show(minHeap);

    // Ausgeben der Anzahl der Elemente in der Min Heap nach dem Löschen des kleinsten Elements
    cout << "Die Anzahl der Elemente in der Min Heap nach dem Löschen des kleinsten Elements beträgt: " << minHeap.size() << endl;

    return 0;
}

Zusammenfassung

In diesem Lab haben wir gelernt, wie man eine Min Heap mit einer Prioritätswarteschlange in C++ implementiert. Wir haben eine Funktion definiert, um die Elemente der Min Heap auszugeben, eine Prioritätswarteschlange von ganzen Zahlen erstellt, sie mit Elementen gefüllt und die Anzahl der Elemente in der Min Heap, das erste Element oder das Element mit der höchsten Priorität, die Elemente der Min Heap, die Min Heap nach dem Löschen des kleinsten Elements und die Anzahl der Elemente in der Min Heap nach dem Löschen des kleinsten Elements ausgegeben.