概要
範囲のヒープ化やヒープ化されているかの判定を行います。
範囲の指定方法は、
・std::xxx(C++03): 対象の範囲 [first, last) のイテレータ―を指定します。
・std::ranges::xxx(C++20): 対象の範囲 [first, last) のイテレータ―を指定します。
・std::ranges::xxx(C++20): 対象の範囲を直接指定します。
条件判定に関数を指定します。※
std::ranges::xxx(C++20): 射影(projection)関数を指定できるものがあります。※
※詳細についてはこちらを参照してください。
https://mappuri.com/program/cpp20-algorithm/
ヒープは1対複数の親子関係を持つ木構造のことです。
ここで扱うヒープは、以下の性質を持ちます。
・親1個に対して子2個
・親のほうが大きいか等しい
・子同士では左側の子のほうが大きいか等しい
・配列やSTLコンテナ(vector)などに格納される
ヒープ化
make_heap
範囲をヒープ化します。
範囲はランダムに読み書き可能である必要があります。
push_heap
ヒープ範囲に要素が追加された範囲を再度ヒープ化します。
範囲はランダムに読み書き可能である必要があります。
pop_heap
ヒープ範囲の先頭の要素を末尾に入れ替え、再度ヒープ化します。
範囲はランダムに読み書き可能である必要があります。
sort_heap
ヒープ範囲をソートします。
範囲はランダムに読み書き可能である必要があります。
make_heap, push_heap, pop_heap, sort_heap のサンプル(C++03)
#include <iostream>
/** r 内の [first, last) の範囲と値を出力 範囲:[0, 9) 値:1 2 3 4 5 4 5 6 6 */
template<class T, class U, class V>
static void output(T&& r, U&& first, V&& last) {
std::cout << "範囲:[" << std::distance(std::begin(r), first) << ", " << std::distance(std::begin(r), last) << ")";
std::cout << " 値:";
std::string delim = "";
for (auto i = first; i != last; ++i, delim = ", ") {
std::cout << delim << *i;
}
std::cout << std::endl;
}
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char* argv[]) {
{
// 範囲をヒープ化します。(C++03)
std::vector<int> r = { 1, 2, 3, 4, 5 };
std::make_heap(r.begin(), r.end());
output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:5, 4, 3, 1, 2
}
{
// ヒープ範囲に要素が追加された範囲を再度ヒープ化します。(C++03)
std::vector<int> r = { 5, 4, 3, 1, 2 };
r.push_back(6);
output(r, r.begin(), r.end()); // 範囲:[0, 6) 値:5, 4, 3, 1, 2, 6
std::push_heap(r.begin(), r.end());
output(r, r.begin(), r.end()); // 範囲:[0, 6) 値:6, 4, 5, 1, 2, 3
}
{
// ヒープ範囲の先頭の要素を末尾に入れ替え、再度ヒープ化します。(C++03)
std::vector<int> r = { 6, 4, 5, 1, 2, 3 };
std::pop_heap(r.begin(), r.end());
output(r, r.begin(), r.end()); // 範囲:[0, 6) 値:5, 4, 3, 1, 2, 6
r.pop_back();
output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:5, 4, 3, 1, 2
}
{
// ヒープ範囲をソートします。(C++03)
std::vector<int> r = { 5, 4, 3, 1, 2 };
std::sort_heap(r.begin(), r.end());
output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:1, 2, 3, 4, 5
}
return 0;
}
make_heap, push_heap, pop_heap, sort_heap のサンプル(C++20 range)
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char* argv[]) {
{
// 範囲をヒープ化します。(C++03)
std::vector<int> r = { 1, 2, 3, 4, 5 };
std::ranges::make_heap(r);
output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:5, 4, 3, 1, 2
}
{
// ヒープ範囲に要素が追加された範囲を再度ヒープ化します。(C++03)
std::vector<int> r = { 5, 4, 3, 1, 2 };
r.push_back(6);
output(r, r.begin(), r.end()); // 範囲:[0, 6) 値:5, 4, 3, 1, 2, 6
std::ranges::push_heap(r);
output(r, r.begin(), r.end()); // 範囲:[0, 6) 値:6, 4, 5, 1, 2, 3
}
{
// ヒープ範囲の先頭の要素を末尾に入れ替え、再度ヒープ化します。(C++03)
std::vector<int> r = { 6, 4, 5, 1, 2, 3 };
std::ranges::pop_heap(r);
output(r, r.begin(), r.end()); // 範囲:[0, 6) 値:5, 4, 3, 1, 2, 6
r.pop_back();
output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:5, 4, 3, 1, 2
}
{
// ヒープ範囲をソートします。(C++03)
std::vector<int> r = { 5, 4, 3, 1, 2 };
std::ranges::sort_heap(r);
output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:1, 2, 3, 4, 5
}
return 0;
}
ヒープ化判定
is_heap
範囲がヒープ化されているか判定します。
範囲はランダムに読み書き可能である必要があります。
is_heap_until
範囲のヒープ化されていない位置を取得します。
範囲はランダムに読み書き可能である必要があります。
is_heap, is_heap_until のサンプル(C++11)
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char* argv[]) {
{
// 範囲がヒープ化されているか判定します。(C++11)
std::vector<int> r = { 5, 4, 3, 1, 2, 6 };
bool is_heap = std::is_heap(r.begin(), r.end());
std::cout << "is_heap = " << std::boolalpha << is_heap << std::endl; // is_heap = false
}
{
// 範囲のヒープ化されていない位置を取得します。(C++11)
std::vector<int> r = { 5, 4, 3, 1, 2, 6 };
auto is_heap_until = std::is_heap_until(r.begin(), r.end());
output(r, is_heap_until); // 位置:5 値:6
}
return 0;
}
is_heap, is_heap_until のサンプル(C++20 range)
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char* argv[]) {
{
// 範囲がヒープ化されているか判定します。(C++20)
std::vector<int> r = { 5, 4, 3, 1, 2, 6 };
bool is_heap = std::ranges::is_heap(r);
std::cout << "is_heap = " << std::boolalpha << is_heap << std::endl; // is_heap = false
}
{
// 範囲のヒープ化されていない位置を取得します。(C++20)
std::vector<int> r = { 5, 4, 3, 1, 2, 6 };
auto is_heap_until = std::ranges::is_heap_until(r);
output(r, is_heap_until); // 位置:5 値:6
}
return 0;
}
コメント