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

FreeBSD Manual Pages

  
 
  

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

NAME
       std::ranges::make_heap -	std::ranges::make_heap

Synopsis
	  Defined in header <algorithm>
	  Call signature
	  template< std::random_access_iterator	I, std::sentinel_for<I>	S,

		    class Comp = ranges::less, class Proj = std::identity >
	  requires	      std::sortable<I,		 Comp,		 Proj>
       (1) (since C++20)
	  constexpr I

	      make_heap( I first, S last, Comp comp = {}, Proj proj = {} );
	  template< ranges::random_access_range	R, class Comp =
	  ranges::less,

		    class	 Proj	     =	       std::identity	     >
       (2) (since C++20)
	  requires std::sortable<ranges::iterator_t<R>,	Comp, Proj>
	  constexpr ranges::borrowed_iterator_t<R>

	      make_heap( R&& r,	Comp comp = {},	Proj proj = {} );

	  Constructs a max heap	in the range [first, last).

	  1)  Elements are compared using the given binary comparison function
       comp and
	  projection object proj.
	  2) Same as (1), but uses r as	the range,  as	if  using  ranges::be-
       gin(r) as first and
	  ranges::end(r) as last.

	  The  function-like  entities	described  on this page	are niebloids,
       that is:

	    * Explicit template	argument lists cannot be specified when	 call-
       ing any of them.
	    * None of them are visible to argument-dependent lookup.
	    *  When  any of them are found by normal unqualified lookup	as the
       name to the left
	      of the function-call operator, argument-dependent	lookup is  in-
       hibited.

	  In  practice,	 they  may be implemented as function objects, or with
       special compiler
	  extensions.

Parameters
	  first, last -	the range of elements to make the heap from
	  r	      -	the range of elements to make the heap from
	  pred	      -	predicate to apply to the projected elements
	  proj	      -	projection to apply to the elements

Return value
	  An iterator equal to last.

Complexity
	  Given	N  =  ranges::distance(first,  last),  at  most	 \(\scriptsize
       3\cdot N\)3*N
	  comparisons and \(\scriptsize	6\cdot N\)6*N projections.

Notes
	  A  max  heap is a range of elements [f, l), arranged with respect to
       comparator comp
	  and projection proj, that has	the following properties:

	    * With N = l - f, p	= f[(i - 1) / 2], and q	= f[i],	for all	0 <  i
       < N, the
	      expression   std::invoke(comp,  std::invoke(proj,	 p),  std::in-
       voke(proj, q))
	      evaluates	to false.
	    *  A  new  element	can  be	 added	using  ranges::push_heap,   in
       \(\scriptsize
	      \mathcal{O}(\log N)\)(log	N) time.
	    *  The  first  element  can	 be removed using ranges::pop_heap, in
       \(\scriptsize
	      \mathcal{O}(\log N)\)(log	N) time.

Example
       // Run this code

	#include <algorithm>
	#include <cmath>
	#include <functional>
	#include <iostream>
	#include <vector>

	void out(const auto& what, int n = 1)
	{
	    while (n-- > 0)
		std::cout << what;
	}

	void print(auto	rem, auto const& v)
	{
	    out(rem);
	    for	(auto e	: v)
		out(e),	out(' ');
	    out('\n');
	}

	void draw_heap(auto const& v)
	{
	    auto bails = [](int	n, int w)
	    {
		auto b = [](int	w) { out(""), out("", w), out(""), out("", w),
       out("");	};
		if (!(n	/= 2))
		    return;
		for (out(' ', w); n-- >	0;)
		    b(w), out('	', w + w + 1);
		out('\n');
	    };

	    auto data =	[](int n, int w, auto& first, auto last)
	    {
		for (out(' ', w); n-- >	0 && first != last; ++first)
		    out(*first), out(' ', w + w	+ 1);
		out('\n');
	    };

	    auto tier =	[&](int	t, int m, auto&	first, auto last)
	    {
		const int n{1 << t};
		const int w{(1 << (m - t - 1)) - 1};
		bails(n, w), data(n, w,	first, last);
	    };

	    const int m{static_cast<int>(std::ceil(std::log2(1 + v.size())))};
	    auto first{v.cbegin()};
	    for	(int i{}; i != m; ++i)
		tier(i,	m, first, v.cend());
	}

	int main()
	{
	    std::vector	h{1, 6,	1, 8, 0, 3, 3, 9, 8, 8,	7, 4, 9, 8, 9};
	    print("source: ", h);

	    std::ranges::make_heap(h);
	    print("\n" "max-heap: ", h);
	    draw_heap(h);

	    std::ranges::make_heap(h, std::greater{});
	    print("\n" "min-heap: ", h);
	    draw_heap(h);
	}

Output:
	source:	1 6 1 8	0 3 3 9	8 8 7 4	9 8 9

	max-heap: 9 8 9	8 8 4 9	6 1 0 7	1 3 8 3
	       9

	   8	   9

	 8   8	 4   9

	6 1 0 7	1 3 8 3

	min-heap: 0 1 1	8 6 3 3	9 8 8 7	4 9 8 9
	       0

	   1	   1

	 8   6	 3   3

	9 8 8 7	4 9 8 9

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

http://cppreference.com		  2024.06.10	     std::ranges::make_heap(3)

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

home | help