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

FreeBSD Manual Pages

  
 
  

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

NAME
       std::pop_heap - std::pop_heap

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

	  Swaps	 the value in the position first and the value in the position
       last-1 and makes
	  the subrange [first, last-1) into a heap. This has the effect	of re-
       moving the first
	  element from the heap	defined	by the range [first, last).

	  The first version of the function uses operator< to compare the ele-
       ments, which
	  makes	the heap a max heap. The  second  uses	the  given  comparison
       function	comp.

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

Return value
	  (none)

Complexity
	  At most 2log(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';

	    std::pop_heap(v.begin(), v.end()); // moves	the largest to the end

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

	    int	largest	= v.back();
	    v.pop_back();  // actually removes the largest element
	    std::cout << "largest element: " <<	largest	<< '\n';

	    std::cout << "heap without largest:	";
	    for	(auto i	: v) std::cout << i << ' ';
	    std::cout << '\n';
	}

Output:
	v: 9 5 4 1 1 3
	after pop_heap:	5 3 4 1	1 9
	largest	element: 9
	heap without largest: 5	3 4 1 1

See also
	  push_heap	   adds	an element to a	max heap
			   (function template)
	  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)
	  sort_heap	   turns a max heap into a range of elements sorted in
       ascending order
			   (function template)
	  ranges::pop_heap removes the largest element from a max heap
	  (C++20)	   (niebloid)

http://cppreference.com		  2022.07.31		      std::pop_heap(3)

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

home | help