C++ で STL ヒープアルゴリズムを使用する
-
std::make_heap関数を使用して、範囲をヒープに変換する -
std::sort_heap関数を使用して、ヒープ範囲をソートする -
std::pop_heap関数を使用して、ヒープ内の次の要素を削除する
この記事では、C++ で STL ヒープアルゴリズムを利用する方法を説明します。
std::make_heap 関数を使用して、範囲をヒープに変換する
std::make_heap 関数は STL アルゴリズムの下で提供され、指定された範囲からバイナリヒープデータ構造を構築するために使用できます。一般に、ヒープデータ構造はツリーベースであり、2つの一般的なタイプは最大ヒープと最小ヒープとして知られています。
最大ヒープでは、どの子ノードでも、その親ノードからのキーは子のキー以上です。一方、親のキーは子のキーと同じではありません。現在、make_heap 関数で構築されたヒープ構造は、バイナリツリーデータ構造に似たバイナリヒープです。ヒープは、対数時間で実行できる要素の挿入および削除操作に効率的であることに注意してください。
次の例は、std::vector プロセスをヒープに変換し、通常の printVector 関数を使用してコンテンツを出力する方法を示しています。要素の順序が少し不思議であることに注意してください。実際、最初の要素がルートキー値であるバイナリツリー構造として読み取ることができます。
二分木のノードごとに最大で 2つの子しかないため、82 と 39 は子としてルートに従います。次の 2つの要素は 82 の子ノードであり、他の 2つは 39 の下に配置されます。この階層は、親要素がその子以上のキーを持つ最大ヒーププロパティを満たします。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
int main() {
vector<int> vec1{11, 82, 39, 72, 51, 32, 91};
cout << "vec1 original: ";
printVector(vec1);
std::make_heap(vec1.begin(), vec1.end());
cout << "vec1 make_heap: ";
printVector(vec1);
return EXIT_SUCCESS;
}
出力：
vec1 original: 11; 82; 39; 72; 51; 32; 91;
vec1 make_heap: 91; 82; 39; 72; 51; 32; 11;
std::sort_heap 関数を使用して、ヒープ範囲をソートする
std::sort_heap 関数を使用すると、std::make_heap 関数を使用して以前に変換された範囲を並べ替えることができます。std::sort_heap 関数の単純なオーバーロードは、2つのイテレータ引数のみを取り、範囲を昇順でソートします。関数の他のオーバーロードは、次のシグネチャを持つ比較関数の 3 番目の引数を受け入れることができます：bool cmp(const Type1 &a, const Type2 &b);。範囲がソートされると、ヒーププロパティはなくなります。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
int main() {
vector<int> vec1{11, 82, 39, 72, 51, 32, 91};
std::make_heap(vec1.begin(), vec1.end());
printVector(vec1);
std::sort_heap(vec1.begin(), vec1.end());
printVector(vec1);
return EXIT_SUCCESS;
}
出力：
91; 82; 39; 72; 51; 32; 11;
11; 32; 39; 51; 72; 82; 91;
std::pop_heap 関数を使用して、ヒープ内の次の要素を削除する
ヒープ構造は通常、要素の高速挿入および削除操作をサポートします。std::push_heap 関数と std::pop_heap 関数は、ヒープ範囲に対してこれらの操作を対応して実行します。ヒープ範囲で std::push_heap コマンドが呼び出されると、その最初の要素が最後の位置と交換され、残りの要素で新しいヒープが構築されます。ヒープは、デフォルトのパラメータで最大ヒープとして構築されることに注意してください。オプションの比較関数を 3 番目の引数として渡して、それに応じてヒープ階層を変更できます。
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
int main() {
vector<int> vec1{11, 82, 39, 72, 51, 32, 91};
std::make_heap(vec1.begin(), vec1.end());
printVector(vec1);
std::pop_heap(vec1.begin(), vec1.end());
printVector(vec1);
return EXIT_SUCCESS;
}
出力：
91; 82; 39; 72; 51; 32; 11;
82; 72; 39; 11; 51; 32; 91;
