std::ranges::make_heap
cppreference.net에서
| 헤더 <algorithm>
|
||
| 호출 시그니처 |
||
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 make_heap( I first, S last, Comp comp = {}, Proj proj = {} );
|
(1) | (C++20부터) |
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>
make_heap( R&& r, Comp comp = {}, Proj proj = {} );
|
(2) | (C++20부터) |
주어진 범위의 요소들로부터 힙을 comp 및 proj에 따라 구성합니다.
1) 지정된 범위는
[first, last)입니다.2) 지정된 범위는
r입니다.이 페이지에 설명된 함수형 개체들은 알고리즘 함수 개체 (비공식적으로 니블로이드라고 함)입니다. 즉:
- 이들 중 하나를 호출할 때 명시적 템플릿 인자 목록을 지정할 수 없습니다.
- 이들 중 어느 것도 인자 종속 조회에 표시되지 않습니다.
- 이들 중 하나가 함수 호출 연산자 왼쪽의 이름으로 일반 비한정 조회에 의해 발견되면, 인자 종속 조회가 억제됩니다.
매개변수
| first, last | - | 수정할 요소들의 범위 를 정의하는 반복자-감시자 쌍 |
| r | - |
수정할 요소들의
range
|
| comp | - | 투영된 요소들에 적용할 비교자 |
| proj | - | 요소들에 적용할 투영 |
반환값
1)
last
2)
ranges::
end
(
r
)
복잡도
최대 3·N 번의 comp 적용과 6·N 번의 proj 적용, 여기서 N 은:
1)
ranges::
distance
(
first, last
)
2)
ranges::
distance
(
r
)
예제
이 코드 실행
#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) |
최대 힙을 정렬된 요소 범위로 변환합니다 (알고리즘 함수 객체) |
| 요소 범위로 최대 힙을 생성합니다 (함수 템플릿) |