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

FreeBSD Manual Pages

  
 
  

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

NAME
       std::make_heap -	std::make_heap

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

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

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

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

	  Compare comp );

	  Constructs  a	max heap in the	range [first, last). 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 to make the heap	from
			 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 3*std::distance(first, last) comparisons.

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 <algorithm>
	#include <functional>
	#include <iostream>
	#include <string_view>
	#include <vector>

	void print(std::string_view text, std::vector<int> const& v = {}) {
	    std::cout << text << ": ";
	    for	(const auto& e : v) std::cout << e << '	';
	    std::cout << '\n';
	}

	int main()
	{
	    print("Max heap");

	    std::vector<int> v { 3, 2, 4, 1, 5,	9 };
	    print("initially, v", v);

	    std::make_heap(v.begin(), v.end());
	    print("after make_heap, v",	v);

	    std::pop_heap(v.begin(), v.end());
	    print("after pop_heap, v", v);

	    auto top = v.back();
	    v.pop_back();
	    print("former top element",	{top});
	    print("after removing the former top element, v", v);

	    print("\nMin heap");

	    std::vector<int> v1	{ 3, 2,	4, 1, 5, 9 };
	    print("initially, v1", v1);

	    std::make_heap(v1.begin(), v1.end(), std::greater<>{});
	    print("after make_heap, v1", v1);

	    std::pop_heap(v1.begin(), v1.end(),	std::greater<>{});
	    print("after pop_heap, v1",	v1);

	    auto top1 =	v1.back();
	    v1.pop_back();
	    print("former top element",	{top1});
	    print("after removing the former top element, v1", v1);
	}

Output:
	Max heap:
	initially, v: 3	2 4 1 5	9
	after make_heap, v: 9 5	4 1 2 3
	after pop_heap,	v: 5 3 4 1 2 9
	former top element: 9
	after removing the former top element, v: 5 3 4	1 2

	Min heap:
	initially, v1: 3 2 4 1 5 9
	after make_heap, v1: 1 2 4 3 5 9
	after pop_heap,	v1: 2 3	4 9 5 1
	former top element: 1
	after removing the former top element, v1: 2 3 4 9 5

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)
	  push_heap	    adds an element to a max heap
			    (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)
	  priority_queue    adapts a container to provide priority queue
			    (class template)
	  ranges::make_heap creates a max heap out of a	range of elements
	  (C++20)	    (niebloid)

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

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

home | help