std::ranges:: make_heap
std::ranges
| Non-modifying sequence operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Modifying sequence operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Partitioning operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Sorting operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Binary search operations (on sorted ranges) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Set operations (on sorted ranges) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Heap operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Minimum/maximum operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Permutation operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Fold operations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Operations on uninitialized storage | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Return types | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
헤더 파일에 정의됨
<algorithm>
|
||
|
함수 호출 시그니처
|
||
|
template
<
std::
random_access_iterator
I,
std::
sentinel_for
<
I
>
S,
class
Comp
=
ranges::
less
,
class
Proj
=
std::
identity
>
|
(1) | (C++20 이후) |
|
template
<
ranges::
random_access_range
R,
class
Comp
=
ranges::
less
,
class
Proj
=
std::
identity
>
|
(2) | (C++20 이후) |
지정된 범위의 요소들로부터 heap 을 comp 와 proj 를 기준으로 구성합니다.
[
first
,
last
)
입니다.
이 페이지에서 설명하는 함수형 개체들은 algorithm function objects (일반적으로 niebloids 로 알려진)입니다. 즉:
- 명시적 템플릿 인수 목록은 이들 중 어느 것을 호출할 때도 지정할 수 없습니다.
- 이들 중 어느 것도 인수 의존 이름 검색 에 보이지 않습니다.
- 이들 중 어느 것이 함수 호출 연산자의 왼쪽 이름으로 일반 비한정 이름 검색 에 의해 발견될 때, 인수 의존 이름 검색 이 억제됩니다.
목차 |
매개변수
| first, last | - | 수정할 요소들의 범위 를 정의하는 반복자-감시자 쌍 |
| r | - |
수정할 요소들의
range
|
| comp | - | 투영된 요소들에 적용할 비교자 |
| proj | - | 요소들에 적용할 투영 |
반환값
복잡도
최대 \(\scriptsize 3\cdot N\) 3·N 번의 comp 적용과 \(\scriptsize 6\cdot N\) 6·N 번의 proj 적용, 여기서 \(\scriptsize N \) N 은:
예제
#include <algorithm> #include <cmath> #include <functional> #include <iostream> #include <vector> void out(const auto& what, int n = 1) { while (n-- > 0) std::cout << what; } void print(auto rem, const auto& v) { out(rem); for (auto e : v) out(e), out(' '); out('\n'); } void draw_heap(const auto& v) { auto bails = [](int n, int w) { auto b = [](int w) { out("┌"), out("─", w), out("┴"), out("─", w), out("┐"); }; if (!(n /= 2)) return; for (out(' ', w); n-- > 0;) b(w), out(' ', w + w + 1); out('\n'); }; auto data = [](int n, int w, auto& first, auto last) { for (out(' ', w); n-- > 0 && first != last; ++first) out(*first), out(' ', w + w + 1); out('\n'); }; auto tier = [&](int t, int m, auto& first, auto last) { const int n{1 << t}; const int w{(1 << (m - t - 1)) - 1}; bails(n, w), data(n, w, first, last); }; const int m{static_cast<int>(std::ceil(std::log2(1 + v.size())))}; auto first{v.cbegin()}; for (int i{}; i != m; ++i) tier(i, m, first, v.cend()); } int main() { std::vector h{1, 6, 1, 8, 0, 3, 3, 9, 8, 8, 7, 4, 9, 8, 9}; print("source: ", h); std::ranges::make_heap(h); print("\n" "max-heap: ", h); draw_heap(h); std::ranges::make_heap(h, std::greater{}); print("\n" "min-heap: ", h); draw_heap(h); }
출력:
source: 1 6 1 8 0 3 3 9 8 8 7 4 9 8 9
max-heap: 9 8 9 8 8 4 9 6 1 0 7 1 3 8 3
9
┌───┴───┐
8 9
┌─┴─┐ ┌─┴─┐
8 8 4 9
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
6 1 0 7 1 3 8 3
min-heap: 0 1 1 8 6 3 3 9 8 8 7 4 9 8 9
0
┌───┴───┐
1 1
┌─┴─┐ ┌─┴─┐
8 6 3 3
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
9 8 8 7 4 9 8 9
참고 항목
|
(C++20)
|
주어진 범위가 최대 힙인지 확인합니다
(알고리즘 함수 객체) |
|
(C++20)
|
최대 힙인 가장 큰 부분 범위를 찾습니다
(알고리즘 함수 객체) |
|
(C++20)
|
최대 힙에 요소를 추가합니다
(알고리즘 함수 객체) |
|
(C++20)
|
최대 힙에서 가장 큰 요소를 제거합니다
(알고리즘 함수 객체) |
|
(C++20)
|
최대 힙을 오름차순으로 정렬된 요소 범위로 변환합니다
(알고리즘 함수 객체) |
|
요소 범위로부터 최대 힙을 생성합니다
(함수 템플릿) |