std::push_heap
ja.cppreference.net より
| ヘッダ <algorithm>
|
||
template< class RandomIt >
void push_heap( RandomIt first, RandomIt last );
|
で定義 (1) | (C++20 から constexpr) |
template< class RandomIt, class Compare >
void push_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (C++20 から constexpr) |
要素を位置 last - 1 で ヒープ [first, last - 1) に挿入します。挿入後のヒープは [first, last) になります。
1) ヒープは
operator<(C++20 まで)std::less{}(C++20 から) に関して比較されます。2) ヒープは
comp に関して比較されます。以下の条件のいずれかが満たされる場合、動作は未定義です:
[first,last - 1)は対応する比較子に関するヒープではありません。
|
は |
| 引数 |
-
| 挿入後に二分ヒープを構成する要素の | 範囲 | を定義するイテレータのペア comp |
| - | 比較関数オブジェクト ( | Compare の要件を満たすオブジェクト)。第一引数が第二引数より小さいtrue場合に を返します。比較関数のシグネチャは以下と同等であるべきです:
シグネチャに |
| 型要件 | ||
-RandomIt は LegacyRandomAccessIterator の要件を満たす必要があります。
| ||
-Compare は Compare の要件を満たす必要があります。
| ||
計算量
N を std::distance(first, last) とすると:
1) log(N) 回以下の
operator<(C++20 まで)std::less{}(C++20 から) を用いた比較。2) log(N) 回以下の比較関数
comp の適用。例
このコードを実行
#include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
void println(std::string_view rem, const std::vector<int>& v)
{
std::cout << rem;
for (int e : v)
std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
std::vector<int> v{3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end());
println("after make_heap: ", v);
v.push_back(6);
println("after push_back: ", v);
std::push_heap(v.begin(), v.end());
println("after push_heap: ", v);
}
出力:
after make_heap: 9 5 4 1 1 3
after push_back: 9 5 4 1 1 3 6
after push_heap: 9 5 6 1 1 3 4
欠陥報告
以下の動作変更欠陥報告は、以前に公開された C++ 標準に遡って適用されました。
| DR | 適用先 | 公開された動作 | 正しい動作 |
|---|---|---|---|
| LWG 3032 | C++98 | の要素は Swappable である必要はありませんでした
[first, last)必須に
|
関連項目 |
is_heap
指定された範囲が最大ヒープかどうか調べます |
(関数テンプレート アルゴリズム関数オブジェクト)&ranges::is_heap |
is_heap_until |
|
最大ヒープである最大の部分範囲を見つけます |
(関数テンプレート アルゴリズム関数オブジェクト)&ranges::is_heap_until |
make_heap |
|
| (関数テンプレート アルゴリズム関数オブジェクト)&ranges::make_heap | |
pop_heap |
|
| (関数テンプレート アルゴリズム関数オブジェクト)&ranges::pop_heap | |
sort_heap |
|
| (関数テンプレート アルゴリズム関数オブジェクト)&ranges::sort_heap | |
ranges::push_heap |
|
要素を最大ヒープに追加します |
(アルゴリズム関数オブジェクト) |