Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::push_heap

      From cppreference.com
      <cpp‎ |algorithm
       
       
      Algorithm library
      Constrained algorithms and algorithms on ranges(C++20)
      Constrained algorithms, e.g.ranges::copy,ranges::sort, ...
      Execution policies(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
      (C++11)
      (C++17)
      Lexicographical comparison operations
      Permutation operations
      C library
      Numeric operations
      Operations on uninitialized memory
       
      Defined in header<algorithm>
      template<class RandomIt>
      void push_heap( RandomIt first, RandomIt last);
      		 (1)(constexpr since C++20)
      template<class RandomIt,class Compare>
      void push_heap( RandomIt first, RandomIt last, Compare comp);
      		 (2)(constexpr since C++20)

      Inserts the element at the positionlast-1 into theheap[first, last-1). The heap after the insertion will be[first, last).

      1) The heap is with respect tooperator<(until C++20)std::less{}(since C++20).
      2) The heap is with respect tocomp.

      If any of the following conditions is satisfied, the behavior is undefined:

      • [first, last-1) is not a heap with respect to the corresponding comparator.
      (until C++11)
      (since C++11)

      Contents

      [edit]Parameters

      first, last - the pair of iterators defining therange of elements that form the binary heap after insertion
      comp - comparison function object (i.e. an object that satisfies the requirements ofCompare) which returnstrue if the first argument isless than the second.

      The signature of the comparison function should be equivalent to the following:

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

      While the signature does not need to haveconst&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const)Type1 andType2 regardless ofvalue category (thus,Type1& is not allowed, nor isType1 unless forType1 a move is equivalent to a copy(since C++11)).
      The typesType1 andType2 must be such that an object of typeRandomIt can be dereferenced and then implicitly converted to both of them.

      Type requirements
      -
      RandomIt must meet the requirements ofLegacyRandomAccessIterator.
      -
      Compare must meet the requirements ofCompare.

      [edit]Complexity

      Given\(\scriptsize N\)N asstd::distance(first, last):

      1) At most\(\scriptsize \log(N)\)log(N) comparisons usingoperator<(until C++20)std::less{}(since C++20).
      2) At most\(\scriptsize \log(N)\)log(N) applications of the comparison functioncomp.

      [edit]Example

      Run this code
      #include <algorithm>#include <iostream>#include <string_view>#include <vector> void println(std::string_view rem,conststd::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);}

      Output:

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

      [edit]Defect reports

      The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

      DRApplied toBehavior as publishedCorrect behavior
      LWG 3032C++98the elements of[first, last) was not required to be swappablerequired

      [edit]See also

      (C++11)
      		 checks if the given range is a max heap
      (function template)[edit]
      finds the largest subrange that is a max heap
      (function template)[edit]
      creates a max heap out of a range of elements
      (function template)[edit]
      removes the largest element from a max heap
      (function template)[edit]
      turns a max heap into a range of elements sorted in ascending order
      (function template)[edit]
      adds an element to a max heap
      (algorithm function object)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/push_heap&oldid=180604"
      [8]ページ先頭
      ©2009-2025 Movatter.jp