C++で両端優先キュー（ダブルエンドプライオリティキュー）を実装する方法

このチュートリアルでは、C++のsetコンテナを使って両端優先キュー（Double-Ended Priority Queue）を実装する方法を解説します。両端優先キューは、最小値と最大値の両方に効率的にアクセスできるデータ構造です。

まず、両端優先キューを作成するための手順を確認しましょう。

• 任意の名前で構造体（struct）を作成します。

• setを使ってキュー本体となる変数を定義します。

• sizeメソッド：キューのサイズを返します。

• is_emptyメソッド：キューが空かどうかを判定して返します。

• insertメソッド：新しい要素をキューに挿入します。

• get_startメソッド：キューの左側（最小値）の要素を返します。

• get_endメソッド：キューの右側（最大値）の要素を返します。

• delete_startメソッド：左側の先頭要素を削除します。

• delete_endメソッド：右側の末尾要素を削除します。

実装例

それでは、実際のコードを見ていきましょう。

#include <bits/stdc++.h>
using namespace std;
struct doubleEndedQueue {
    set<int> s;
    int size() {
        return s.size();
    }
    string is_empty() {
        return s.size() == 0 ? "True" : "False";
    }
    void insert(int x) {
        s.insert(x);
    }
    int get_start() {
        return *(s.begin());
    }
    int get_end() {
        return *(s.rbegin());
    }
    void delete_start() {
        if (s.size() == 0) {
            return;
        }
        s.erase(s.begin());
    }
    void delete_end() {
        if (s.size() == 0) {
            return;
        }
        auto end = s.end();
        end--;
        s.erase(end);
    }
};
int main() {
    doubleEndedQueue d;
    cout << "is empty: " << d.is_empty() << endl;
    d.insert(1);
    d.insert(2);
    d.insert(3);
    d.insert(4);
    d.insert(5);
    cout << "is empty: " << d.is_empty() << endl;
    cout << "end: " << d.get_end() << endl;
    d.delete_end();
    cout << "end: " << d.get_end() << endl;
    cout << "start: " << d.get_start() << endl;
    d.delete_start();
    cout << "start: " << d.get_start() << endl;
    return 0;
}

実行結果

上記のコードを実行すると、以下のような結果が出力されます。

is empty: True
is empty: False
end: 5
end: 4
start: 1
start: 2

実装のポイント

C++のsetは内部で要素を常にソートされた状態で保持するため、begin()で最小値、rbegin()で最大値にそれぞれ定数時間でアクセスできます。また、重複した値は自動的に除外されるため、ユニークな要素のみを扱う両端優先キューとして機能します。削除操作の前に空チェックを行っている点も、安全な実装として重要なポイントです。

まとめ

本チュートリアルでは、setを活用した両端優先キューの基本的な実装方法を学びました。挿入・削除・両端からの参照といった操作を、シンプルな構造体で効率よく実現できます。チュートリアルの内容について質問がある場合は、コメント欄でお気軽にお知らせください。