C++ での優先度付きキューの実装

はじめに

この実験では、C++ プログラミング言語における優先度付きキューの基本機能について学びます。優先度付きキューは、C++ STL（Standard Template Library）のコンテナであり、要素をその優先度に応じて挿入および削除できるようにします。最も高い優先度を持つ要素は常にキューの先頭に配置されます。要素がキューから削除されると、優先度付きキューは自動的に次に高い優先度の要素を正しい位置に挿入することを担当します。

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("C++")) -.-> cpp/IOandFileHandlingGroup(["I/O and File Handling"]) cpp(("C++")) -.-> cpp/StandardLibraryGroup(["Standard Library"]) cpp(("C++")) -.-> cpp/SyntaxandStyleGroup(["Syntax and Style"]) cpp(("C++")) -.-> cpp/ControlFlowGroup(["Control Flow"]) cpp/ControlFlowGroup -.-> cpp/for_loop("For Loop") cpp/ControlFlowGroup -.-> cpp/while_loop("While Loop") cpp/IOandFileHandlingGroup -.-> cpp/output("Output") cpp/StandardLibraryGroup -.-> cpp/standard_containers("Standard Containers") cpp/SyntaxandStyleGroup -.-> cpp/code_formatting("Code Formatting") subgraph Lab Skills cpp/for_loop -.-> lab-96225{{"優先度付きキューの実装"}} cpp/while_loop -.-> lab-96225{{"優先度付きキューの実装"}} cpp/output -.-> lab-96225{{"優先度付きキューの実装"}} cpp/standard_containers -.-> lab-96225{{"優先度付きキューの実装"}} cpp/code_formatting -.-> lab-96225{{"優先度付きキューの実装"}} end

必要なライブラリをインクルードする

以下のコマンドを使用して、~/project ディレクトリに新しいファイル main.cpp を作成します。

touch ~/project/main.cpp

まず、プログラムが正常に動作するために必要なライブラリをインクルードする必要があります。このプログラムでは、iostream と bits/stdc++.h ライブラリを使用します。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

show関数を定義する

show 関数は、優先度付きキューに存在するすべての要素を表示するために使用されます。この関数は、優先度付きキューオブジェクトを引数として取り、元の優先度付きキューを維持するためにキューを別のものにコピーします。その後、優先度付きキューを反復処理して、その中に存在するすべての要素を出力します。

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top(); //一番上の要素を出力
        pq.pop();                 //一番上の要素を削除して次の要素に移動
    }
    cout << endl;
}

メイン関数を実装する

main 関数は、すべての処理が行われる場所です。まず、整数型の変数 i を宣言します。その後、整数型の優先度付きキュー q を作成します。そして、push 関数を使っていくつかの整数を優先度付きキューに追加します。

その後、show 関数を使って優先度付きキューに存在する要素を表示します。次に、size 関数を使ってキューに存在する要素の数を表示し、top 関数を使って最も高い優先度を持つ要素を表示します。

次に、pop 関数を使って最も高い優先度を持つ要素を削除し、show 関数を使って更新された優先度付きキューを表示します。

int main()
{
    priority_queue<int> q;

    for (int i = 1; i < 6; i++)
    {
        q.push(i * 10);
    }

    cout << "The Priority Queue is: ";
    show(q);

    cout << "\n\nThe number of elements in the Priority Queue are: " << q.size();

    cout << "\n\nThe element with the highest priority is: " << q.top();

    q.pop();
    cout << "\n\nAfter Deleting the top most element, Priority Queue becomes: ";
    show(q);

    return 0;
}

最終コード

C++ で優先度付きキューを実装するには、以下のコードを使用できます。

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

using namespace std;

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top();
        pq.pop();
    }
    cout << endl;
}

int main()
{
    priority_queue<int> q;

    for (int i = 1; i < 6; i++)
    {
        q.push(i * 10);
    }

    cout << "The Priority Queue is: ";
    show(q);

    cout << "\n\nThe number of elements in the Priority Queue are: " << q.size();

    cout << "\n\nThe element with the highest priority is: " << q.top();

    q.pop();
    cout << "\n\nAfter Deleting the top most element, Priority Queue becomes: ";
    show(q);

    return 0;
}

上記のコードを ~/project/main.cpp に保存します。このコードをコンパイルして実行するには、以下のコマンドを使用します。

g++ main.cpp -o main &&./main

まとめ

この実験では、C++ における優先度付きキューの基本概念について学びました。また、優先度付きキューを宣言および初期化する方法と、そこから要素を追加、削除、表示する方法も見てきました。このチュートリアルが役に立ったことを願っています。