C++ のミニヒープ | 優先度キュープログラミングチュートリアル

はじめに

この実験では、C++ で優先度キューを使ってミニヒープを実装する方法を学びます。ミニヒープで基本的な操作を行うことができる C++ プログラムを実装します。

新しい C++ プログラムを作成する

ターミナルで以下のコマンドを実行して、~/project ディレクトリに新しい C++ プログラムを作成します。

cd ~/project
touch main.cpp

必要なヘッダーファイルをインクルードする

まず、プログラムに必要なヘッダーファイルをインクルードします。

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

using namespace std;

show() 関数を定義する

次に、ミニヒープの要素を表示する関数を定義します。この関数は優先度キューを引数として取り、元の優先度キューを維持するために優先度キューのコピーを使用します。

// ミニヒープの要素を表示する関数
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // 元の優先度キューを維持するために、優先度キューを別のものにコピーする
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // 最上位の要素を表示する
        mh.pop();                 // 最上位の要素を削除して次の要素に移動する
    }

    cout << endl;
}

main() 関数を実装する

main() 関数では、整数の優先度キューを作成し、それに要素を追加します。

int main()
{
    // 整数の優先度キューを作成する
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 優先度キューに要素を追加する
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // ミニヒープ内の要素数を表示する
    cout << "The number of elements in the Min Heap are : " << minHeap.size() << endl;

    // 最初の要素または最も高い優先度の要素を表示する
    cout << "The first element or the element with the highest priority is: " << minHeap.top() << endl;

    // ミニヒープの要素を表示する
    cout << "The elements of the Min Heap are: ";
    show(minHeap);

    // ミニヒープから最初のまたは最小の要素を削除する
    minHeap.pop();

    // 最小の要素を削除した後のミニヒープを表示する
    cout << "After Deleting the first or the smallest element from the Min Heap, it becomes: ";
    show(minHeap);

    // 最小の要素を削除した後のミニヒープ内の要素数を表示する
    cout << "The number of elements in the Min Heap after deleting the smallest element are : " << minHeap.size() << endl;

    return 0;
}

プログラムをコンパイルして実行する

プログラムをコンパイルするには、ターミナルで以下のコマンドを実行します。

g++ main.cpp -o main

このコマンドは、main.cpp のソースコードをコンパイルし、main という名前の実行可能ファイルを作成します。

プログラムを実行するには、以下のコマンドを実行します。

./main

main.cpp の完全なコード

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

using namespace std;

// ミニヒープの要素を表示する関数
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // 元の優先度キューを維持するために、優先度キューを別のものにコピーする
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // 最上位の要素を表示する
        mh.pop();                 // 最上位の要素を削除して次の要素に移動する
    }

    cout << endl;
}

int main()
{
    // 整数の優先度キューを作成する
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 優先度キューに要素を追加する
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // ミニヒープ内の要素数を表示する
    cout << "The number of elements in the Min Heap are : " << minHeap.size() << endl;

    // 最初の要素または最も高い優先度の要素を表示する
    cout << "The first element or the element with the highest priority is: " << minHeap.top() << endl;

    // ミニヒープの要素を表示する
    cout << "The elements of the Min Heap are: ";
    show(minHeap);

    // ミニヒープから最初のまたは最小の要素を削除する
    minHeap.pop();

    // 最小の要素を削除した後のミニヒープを表示する
    cout << "After Deleting the first or the smallest element from the Min Heap, it becomes: ";
    show(minHeap);

    // 最小の要素を削除した後のミニヒープ内の要素数を表示する
    cout << "The number of elements in the Min Heap after deleting the smallest element are : " << minHeap.size() << endl;

    return 0;
}

まとめ

この実験では、C++ で優先度キューを使ってミニヒープを実装する方法を学びました。ミニヒープの要素を表示する関数を定義し、整数の優先度キューを作成し、それに要素を追加し、ミニヒープ内の要素数、最初の要素または最も高い優先度の要素、ミニヒープの要素、最小の要素を削除した後のミニヒープ、および最小の要素を削除した後のミニヒープ内の要素数を表示しました。

優先度キューを使ったミニヒープの実装