Namespaces
Variants

std:: make_heap

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
헤더 파일에 정의됨 <algorithm>
template < class RandomIt >
void make_heap ( RandomIt first, RandomIt last ) ;
(1) (constexpr since C++20)
template < class RandomIt, class Compare >
void make_heap ( RandomIt first, RandomIt last, Compare comp ) ;
(2) (constexpr since C++20)

범위 [ first , last ) 에 힙 을 구성합니다.

1) 구성된 힙은 operator < (C++20 이전) std:: less { } (C++20 이후) 에 기반합니다.
2) 구성된 힙은 comp 에 대한 것입니다.

다음 조건 중 하나라도 충족되면, 동작은 정의되지 않습니다:

(C++11 이전)
(C++11 이후)

목차

매개변수

first, last - 이진 힙을 만들 요소들의 범위 를 정의하는 반복자 쌍
comp - 비교 함수 객체(즉, Compare 요구 사항을 만족하는 객체)로, 첫 번째 인수가 두 번째 인수보다 작은 경우 true 를 반환합니다.

비교 함수의 시그니처는 다음에 해당해야 합니다:

bool cmp ( const Type1 & a, const Type2 & b ) ;

시그니처에 const & 가 필요하지는 않지만, 함수는 전달된 객체를 수정해서는 안 되며 값 범주 에 관계없이 (가능한 const) Type1 및 Type2 타입의 모든 값을 수용할 수 있어야 합니다 (따라서 Type1 & 는 허용되지 않으며, Type1 에 대해 이동이 복사와 동등하지 않는 한 Type1 도 허용되지 않습니다 (C++11부터) ).
Type1 및 Type2 타입은 RandomIt 타입의 객체가 역참조된 후 두 타입 모두로 암시적으로 변환될 수 있어야 합니다.

타입 요구 사항
-
RandomIt 는 LegacyRandomAccessIterator 요구 사항을 충족해야 합니다.
-
Compare 는 Compare 요구 사항을 충족해야 합니다.

복잡도

주어진 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 ) 범위의 요소들이 swappable할 필요가 없었음 필요함

참고 항목

(C++11)
주어진 범위가 최대 힙인지 확인합니다
(함수 템플릿)
(C++11)
최대 힙인 가장 큰 부분 범위를 찾습니다
(함수 템플릿)
최대 힙에 요소를 추가합니다
(함수 템플릿)
최대 힙에서 가장 큰 요소를 제거합니다
(함수 템플릿)
최대 힙을 오름차순으로 정렬된 요소 범위로 변환합니다
(함수 템플릿)
컨테이너를 우선순위 큐로 적응시킵니다
(클래스 템플릿)
(C++20)
요소 범위로부터 최대 힙을 생성합니다
(알고리즘 함수 객체)