std::ranges:: push_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 이후) |
지정된 범위의 마지막 요소를 힙 에 삽입합니다. 이때 힙은 마지막 요소를 제외한 범위의 모든 요소로 구성되며, comp 와 proj 를 기준으로 합니다. 삽입 후의 힙은 전체 범위가 됩니다.
[
first
,
last
)
입니다.
지정된 범위(마지막 요소 제외)가 comp 와 proj 에 대해 힙이 아닌 경우, 동작은 정의되지 않습니다.
이 페이지에서 설명하는 함수형 개체들은 algorithm function objects (일반적으로 niebloids 로 알려진)입니다. 즉:
- 명시적 템플릿 인수 목록은 이들 중 어느 것을 호출할 때도 지정할 수 없습니다.
- 이들 중 어느 것도 인수 의존 이름 검색 에 보이지 않습니다.
- 이들 중 어느 것이 일반 비한정 이름 검색 에 의해 함수 호출 연산자의 왼쪽 이름으로 발견될 때, 인수 의존 이름 검색 이 억제됩니다.
목차 |
매개변수
| first, last | - | 수정할 요소들의 범위 를 정의하는 반복자-감시자 쌍 |
| r | - |
수정할 요소들의
range
|
| comp | - | 투영된 요소들에 적용할 비교자 |
| proj | - | 요소들에 적용할 투영 |
반환값
복잡도
최대 \(\scriptsize \log{(N)}\) log(N) 번의 comp 적용과 \(\scriptsize 2\log{(N)}\) 2log(N) 번의 proj 적용, 여기서 \(\scriptsize N \) N 은:
가능한 구현
struct push_heap_fn { template<std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<I, Comp, Proj> constexpr I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const { const auto n{ranges::distance(first, last)}; const auto length{n}; if (n > 1) { I last{first + n}; n = (n - 2) / 2; I i{first + n}; if (std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *--last))) { std::iter_value_t<I> v {ranges::iter_move(last)}; do { *last = ranges::iter_move(i); last = i; if (n == 0) break; n = (n - 1) / 2; i = first + n; } while (std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, v))); *last = std::move(v); } } return first + length; } template<ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity> requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> operator()(R&& r, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj)); } }; inline constexpr push_heap_fn push_heap{}; |
예제
#include <algorithm> #include <cmath> #include <iostream> #include <vector> void out(const auto& what, int n = 1) { while (n-- > 0) std::cout << what; } void print(auto rem, auto const& v) { out(rem); for (auto e : v) out(e), out(' '); out('\n'); } void draw_heap(auto const& 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<int> v{1, 6, 1, 8, 0, 3,}; print("source vector v: ", v); std::ranges::make_heap(v); print("after make_heap: ", v); draw_heap(v); v.push_back(9); print("before push_heap: ", v); draw_heap(v); std::ranges::push_heap(v); print("after push_heap: ", v); draw_heap(v); }
출력:
source vector v: 1 6 1 8 0 3 after make_heap: 8 6 3 1 0 1 8 ┌─┴─┐ 6 3 ┌┴┐ ┌┴┐ 1 0 1 before push_heap: 8 6 3 1 0 1 9 8 ┌─┴─┐ 6 3 ┌┴┐ ┌┴┐ 1 0 1 9 after push_heap: 9 6 8 1 0 1 3 9 ┌─┴─┐ 6 8 ┌┴┐ ┌┴┐ 1 0 1 3
참고 항목
|
(C++20)
|
주어진 범위가 최대 힙인지 확인합니다
(알고리즘 함수 객체) |
|
(C++20)
|
최대 힙인 가장 큰 부분 범위를 찾습니다
(알고리즘 함수 객체) |
|
(C++20)
|
요소 범위로부터 최대 힙을 생성합니다
(알고리즘 함수 객체) |
|
(C++20)
|
최대 힙에서 가장 큰 요소를 제거합니다
(알고리즘 함수 객체) |
|
(C++20)
|
최대 힙을 오름차순으로 정렬된 요소 범위로 변환합니다
(알고리즘 함수 객체) |
|
최대 힙에 요소를 추가합니다
(함수 템플릿) |