std::make_heap
ja.cppreference.net より
| ヘッダ <algorithm>
|
||
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );
|
(1) | (C++20からconstexpr) |
template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (C++20からconstexpr) |
範囲 ヒープ を [first, last) 内に構築します。
1) 構築されるヒープは
operator<(C++20まで)std::less{}(C++20から) に関してです。2) 構築されるヒープは
comp に関してです。以下の条件のいずれかが満たされる場合、動作は未定義です:
|
(C++11まで) |
|
(C++11から) |
引数
| first, last | - | 二分ヒープ範囲にする要素の 範囲 を定義するイテレータのペア |
| comp | - | 比較関数オブジェクト（Compare の要件を満たすオブジェクト）。第一引数が第二引数よりtrue小さい場合に を返します。比較関数のシグネチャは以下と同等であるべきです:
シグネチャに |
| 型要件 | ||
-RandomIt は LegacyRandomAccessIterator の要件を満たす必要があります。
| ||
-Compare は Compare の要件を満たす必要があります。
| ||
計算量
N を N として、 std::distance(first, last) とする:
1) 最大 3N 回の
operator<(C++20まで)std::less{}(C++20から) を用いた比較。2) 最大 3N 回の比較関数
comp の適用。例
このコードを実行
#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <vector>
void print(std::string_view text, const std::vector<int>& v = {})
{
std::cout << text << ": ";
for (const auto& e : v)
std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
print("Max heap");
std::vector<int> v{3, 2, 4, 1, 5, 9};
print("initially, v", v);
std::make_heap(v.begin(), v.end());
print("after make_heap, v", v);
std::pop_heap(v.begin(), v.end());
print("after pop_heap, v", v);
auto top = v.back();
v.pop_back();
print("former top element", {top});
print("after removing the former top element, v", v);
print("\nMin heap");
std::vector<int> v1{3, 2, 4, 1, 5, 9};
print("initially, v1", v1);
std::make_heap(v1.begin(), v1.end(), std::greater<>{});
print("after make_heap, v1", v1);
std::pop_heap(v1.begin(), v1.end(), std::greater<>{});
print("after pop_heap, v1", v1);
auto top1 = v1.back();
v1.pop_back();
print("former top element", {top1});
print("after removing the former top element, v1", v1);
}
出力:
Max heap:
initially, v: 3 2 4 1 5 9
after make_heap, v: 9 5 4 1 2 3
after pop_heap, v: 5 3 4 1 2 9
former top element: 9
after removing the former top element, v: 5 3 4 1 2
Min heap:
initially, v1: 3 2 4 1 5 9
after make_heap, v1: 1 2 4 3 5 9
after pop_heap, v1: 2 3 4 9 5 1
former top element: 1
after removing the former top element, v1: 2 3 4 9 5
欠陥報告
以下の振る舞いを変更する欠陥報告は以前に公開された C++ 標準に遡って適用されました。
| DR | 適用先 | 公開時の動作 | 正しい動作 |
|---|---|---|---|
| LWG 3032 | C++98 | の要素がスワップ可能であることが要求されていなかった
[first, last)要求された
|
必須 |
関連項目
(C++11) |
指定された範囲が最大ヒープかどうか調べる (関数テンプレート & アルゴリズム関数オブジェクト) |
(C++20) |
|
(C++11) |
最大ヒープである最大の部分範囲を見つける (関数テンプレート & アルゴリズム関数オブジェクト) |
(C++20) |
|
| 要素を最大ヒープに追加する (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
| 最大ヒープから最大の要素を削除する (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
| 最大ヒープを昇順にソートされた要素の範囲に変換する (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
| コンテナを適応させて優先度付きキューを提供する (クラステンプレート) | |
(C++20) |
要素の範囲から最大ヒープを作成する (アルゴリズム関数オブジェクト) |