1. 導入：なぜ優先度付きキューが重要なのか
プログラミングにおいて、常に「最大値（または最小値）」を取り出したいという場面は頻繁に発生します。例えば、タスクスケジューリングや経路探索（Aアルゴリズムなど）がその代表例です。単純に配列をソートし続けると効率が悪化しますが、C++の標準ライブラリ（STL）が提供する「優先度付きキュー」を活用すれば、この課題を効率的に解決できます。
2. 基礎知識：二分ヒープの仕組み
std::priority_queue の内部では「二分ヒープ」というデータ構造が使われています。これは、木構造をポインタで繋ぐのではなく、std::vector のようなフラットな配列上で管理する手法です。
配列のインデックスを i としたとき、その子要素は 2i+1 と 2i+2 という算術演算で即座に特定できます。これにより、ポインタを辿るメモリ移動が不要となり、CPUのキャッシュ効率が飛躍的に向上します。
3. 実装と解決策
STLでは、優先度付きキューを扱う手段として、コンテナアダプタである std::priority_queue と、既存のコンテナをヒープ化する std::make_heap の2通りが提供されています。
- std::priority_queue: キューとしての振る舞いをカプセル化した使いやすいインタフェースです。
- std::make_heap: すでにある vector に対して、その場でヒープ構造を構築するアルゴリズムです。メモリを節約したい場合や、既存のコンテナを再利用したい場合に最適です。
4. サンプルプログラム
以下のコードでは、std::priority_queue の基本操作と、std::make_heap を使った効率的な配列操作の両方を紹介します。
include <iostream>
include <vector>
include <queue>
include <algorithm>
int main() {
// 1. std::priority_queue の使い方
std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
std::cout << "priority_queue から最大値を取得: " << pq.top() << std::endl;
// 2. std::vector をヒープ化する std::make_heap の使い方
std::vector<int> v = {10, 30, 20, 5, 15};
// ベクタをヒープ構造に変換
std::make_heap(v.begin(), v.end());
// 最大値を取り出すには pop_heap を使用して末尾に移動させる
std::pop_heap(v.begin(), v.end());
int max_val = v.back();
v.pop_back(); // 実際に末尾から削除
std::cout << "make_heap で取得した最大値: " << max_val << std::endl;
return 0;
}
5. 応用・注意点
現場での開発において特に意識すべき点は「キャッシュ効率」と「比較コスト」です。
- キャッシュ効率: std::set や std::map はノードごとにメモリが離散しがちですが、std::priority_queue は配列を直接操作するため、現代のCPUアーキテクチャでは圧倒的に高速です。
- デフォルトの挙動: std::priority_queue はデフォルトで「最大値」が優先されます。最小値を優先したい場合は、テンプレート引数に std::greater を指定してください（例: std::priority_queue<int, std::vector<int>, std::greater<int>>）。
- 注意点: ヒープ構造は「常に最大値を取得する」ことには長けていますが、特定の要素を高速に検索したり、順序を維持したまま全要素を走査したりする用途には向きません。用途に応じて std::set 等と使い分けるのがプロの設計です。
コメント