Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

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) (const-
       expr since C++20)
	  void push_heap( RandomIt first, RandomIt last	);
	  template< class RandomIt, class Compare >
	  void push_heap( RandomIt first, RandomIt last, Compare   (2) (const-
       expr 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 un-
       defined:

	    * [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  sat-
       isfies the
			 requirements  of  Compare)  which returns true	if the
       first argument is
			 less than the second.

			 The signature of the comparison  function  should  be
       equivalent 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  re-
       gardless	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 compar-
       ison 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
       Correct behavior
	  LWG  3032  C++98	the elements of	[first,	last) was not required
       required
			      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)

Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::push_heap&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>

home | help