Namespaces
Variants

    std::push_heap

    cppreference.net에서
     
    C++
     
    알고리즘 라이브러리
    제약된 알고리즘 및 범위에 대한 알고리즘 (C++20)
    예를 들어 제약된 알고리즘ranges::copy, ranges::sort, ...
    정렬 및 관련 연산
    분할 연산
    (C++11)    
    (C++11)

    정렬 연산
    이진 검색 연산
    (분할된 범위에서)
    집합 연산 (정렬된 범위에서)
    병합 연산 (정렬된 범위에서)
    힙 연산
    최소/최대 연산
    (C++11)
    (C++17)
    사전식 비교 연산
    (C++20)
    순열 연산


     
    헤더 <algorithm> 
    template< class RandomIt >
void push_heap( RandomIt first, RandomIt last );
    		에 정의됨 (1) (constexpr, C++20부터) 
    template< class RandomIt, class Compare >
void push_heap( RandomIt first, RandomIt last, Compare comp );
    		(2) (constexpr, C++20부터)

    위치 last - 1의 요소를 힙 [first, last - 1)에 삽입합니다. 삽입 후 힙은 [first, last)이 됩니다.

    1) 힙은 operator<(C++20까지)std::less{}(C++20부터)에 대해 정렬됩니다.
    2) 힙은 comp에 대해 정렬됩니다.

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

    • [first, last - 1)이 해당 비교자에 대해 힙이 아닙니다.
    (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) 최대 log(N) 번의 비교를 사용하며, operator < (C++20 이전) std:: less { } (C++20 이후) 를 사용합니다.
    2) 최대 log(N) 번의 비교 함수 comp 적용.

    예제

    이 코드 실행 
    #include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
void println(std::string_view rem, const std::vector<int>& v)
{
    std::cout << rem;
    for (int e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9};
    std::make_heap(v.begin(), v.end());
    println("after make_heap: ", v);
    v.push_back(6);
    println("after push_back: ", v);
    std::push_heap(v.begin(), v.end());
    println("after push_heap: ", v);
}

    출력: 

    after make_heap: 9 5 4 1 1 3
after push_back: 9 5 4 1 1 3 6
after push_heap: 9 5 6 1 1 3 4

    결함 보고서

    다음의 동작 변경 결함 보고서들은 이전에 발표된 C++ 표준에 소급 적용되었습니다.

    DR 적용 대상 게시된 동작 올바른 동작
    LWG 3032 C++98 [ first , last ) 범위의 요소들이 교환 가능할 필요가 없었음 필요함

    참고

    (C++11)
    		 주어진 범위가 최대 힙인지 확인합니다
    (함수 템플릿 &알고리즘 함수 객체)
    (C++20)
    (C++11)
    		 최대 힙인 가장 큰 하위 범위를 찾습니다
    (함수 템플릿 &알고리즘 함수 객체)
    (C++20)
    		요소의 범위에서 최대 힙을 만듭니다
    (함수 템플릿 &알고리즘 함수 객체)
    (C++20)
    		최대 힙에서 가장 큰 요소를 제거합니다
    (함수 템플릿 &알고리즘 함수 객체)
    (C++20)
    		최대 힙을 오름차순으로 정렬된 요소의 범위로 변환합니다
    (함수 템플릿 &알고리즘 함수 객체)
    (C++20)
    (C++20)
    		 최대 힙에 요소를 추가합니다
    (알고리즘 함수 객체)