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  >				(until
       C++20)
	  void push_heap( RandomIt first, RandomIt last	);
	  template< class RandomIt >
	  constexpr  void  push_heap(  RandomIt	 first,			(since
       C++20)
	  RandomIt last	);
	  template< class RandomIt, class Compare >

	  void	  push_heap(	RandomIt    first,    RandomIt	 last,	   (1)
       (until C++20)

	  Compare comp );
	  template< class RandomIt, class Compare >	       (2)

	  constexpr	  void	      push_heap(	RandomIt	first,
       (since C++20)
	  RandomIt last,

	  Compare comp );

	  Inserts the element at the position last-1 into the max heap defined
       by the range
	  [first, last-1). The first version of	the function uses operator< to
       compare the
	  elements, the	second uses the	given comparison function comp.

Parameters
	  first, last -	 the range of elements defining	the heap to modify
			 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.
	  -
	  The type of dereferenced RandomIt  must  meet	 the  requirements  of
       MoveAssignable and
	  MoveConstructible.

Return value
	  (none)

Complexity
	  At most log(N) comparisons where N=std::distance(first, last).

Notes
	  A max	heap is	a range	of elements [f,l) that has the following prop-
       erties:

		     *	With  N	 = l-f,	for all	0 < i <	N, f[(i-1)/2] does not
       compare less than
		       f[i].
		     * A new element can be  added  using  std::push_heap,  in
       \(\scriptsize
		       \mathcal{O}(\log	N)\)(log N) time.
		     *	The  first element can be removed using	std::pop_heap,
       in \(\scriptsize
		       \mathcal{O}(\log	N)\)(log N) time.

Example
       // Run this code

	#include <iostream>
	#include <algorithm>
	#include <vector>

	int main()
	{
	    std::vector<int> v { 3, 1, 4, 1, 5,	9 };

	    std::make_heap(v.begin(), v.end());

	    std::cout << "v: ";
	    for	(auto i	: v) std::cout << i << ' ';
	    std::cout << '\n';

	    v.push_back(6);

	    std::cout << "before push_heap: ";
	    for	(auto i	: v) std::cout << i << ' ';
	    std::cout << '\n';

	    std::push_heap(v.begin(), v.end());

	    std::cout << "after	push_heap:  ";
	    for	(auto i	: v) std::cout << i << ' ';
	    std::cout << '\n';
	}

Output:
	v: 9 5 4 1 1 3
	before push_heap: 9 5 4	1 1 3 6
	after push_heap:  9 5 6	1 1 3 4

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		  2022.07.31		     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.0>

home | help