home | help 
std::push_heap(3)	       C++ Standard Libary	       std::push_heap(3)

NAME
     std::push_heap - std::push_heap

Synopsis
	Defined in header <algorithm>
	template<  class RandomIt >				  (1) (constexpr
     since C++20)
	void push_heap( RandomIt first, RandomIt last );
	template< class RandomIt, class Compare >
	void push_heap( RandomIt first, RandomIt last, Compare	 (2)  (constexpr
     since C++20)
	comp );

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

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

	If any of the following conditions is satisfied, the behavior  is  unde-
     fined:

	  * [first, last - 1) is not a heap.

	  * The type of *first is not Swappable.	   (until C++11)
	  * RandomIt is not ValueSwappable.
	  * The type of *first is not MoveConstructible.   (since C++11)
	  * The type of *first is not MoveAssignable.

Parameters
	first, last -  the range indicating the heap after the insertion
		       comparison function object (i.e. an object that satisfies
     the
		       requirements  of Compare) which returns true if the first
     argument is
		       less than the second.

		       The signature of the comparison function should be equiv-
     alent to the
		       following:

		       bool cmp(const Type1& a, const Type2& b);
	comp	    -
		       While the signature does not need  to  have  const&,  the
     function must
		       not  modify  the objects passed to it and must be able to
     accept all
		       values of type (possibly const) Type1 and  Type2  regard-
     less of value
		       category (thus, Type1& is not allowed
		       , nor is Type1 unless for Type1 a move is equivalent to a
     copy
		       (since C++11)).
		       The  types Type1 and Type2 must be such that an object of
     type
		       RandomIt can be dereferenced  and  then	implicitly  con-
     verted to both of
		       them.

Type requirements
	-
	RandomIt must meet the requirements of LegacyRandomAccessIterator.
	-
	Compare must meet the requirements of Compare.

Complexity
	Given \(\scriptsize N\)N as std::distance(first, last):

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

Example
     // Run this code

      #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);
      }

Output:
      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

	Defect reports

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

	   DR	 Applied to		 Behavior as published		    Cor-
     rect behavior
	LWG  3032 C++98      the elements of [first, last) was not required  re-
     quired
			    to be swappable

See also
	is_heap 	  checks if the given range is a max heap
	(C++11) 	  (function template)
	is_heap_until	  finds the largest subrange that is a max heap
	(C++11) 	  (function template)
	make_heap	  creates a max heap out of a range of elements
			  (function template)
	pop_heap	  removes the largest element from a max heap
			  (function template)
			  turns a max heap into a range of  elements  sorted  in
     ascending
	sort_heap	  order
			  (function template)
	ranges::push_heap adds an element to a max heap
	(C++20) 	  (niebloid)

http://cppreference.com 	   2024.06.10		       std::push_heap(3)
home | help