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

FreeBSD Manual Pages

  
 
  

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

NAME
       std::ranges::sort_heap -	std::ranges::sort_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

	      sort_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>

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

	  Converts the max heap	[first,	last) into a sorted range in ascending
       order. The
	  resulting range no longer has	the heap property.

	  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 sort
	  r	      -	the range of elements to sort
	  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
       2N\log{(N)}\)2Nlog(N)
	  comparisons and \(\scriptsize	4N\log{(N)}\)4Nlog(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.

Possible implementation
       struct sort_heap_fn {
	   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>
	   constexpr I
	       operator()(I first, S last, Comp	comp = {},  Proj  proj	=  {})
       const
	   {
	       auto ret	{ranges::next(first, last)};
	       for (; first != last; --last)
		   ranges::pop_heap(first, last, comp, proj);
	       return ret;
	   }

	   template<ranges::random_access_range	R, class Comp =	ranges::less,
		    class Proj = std::identity>
	   requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
	   constexpr ranges::borrowed_iterator_t<R>
	       operator()(R&& r, Comp comp = {}, Proj proj = {}) const
	   {
	       return	      (*this)(ranges::begin(r),	       ranges::end(r),
       std::move(comp),	std::move(proj));
	   } };

       inline constexpr	sort_heap_fn sort_heap {};

Example
       // Run this code

	#include <algorithm>
	#include <array>
	#include <iostream>

	void print(auto	const& rem, auto const&	v)
	{
	    std::cout << rem;
	    for	(const auto i :	v)
		std::cout << i << ' ';
	    std::cout << '\n';
	}

	int main()
	{
	    std::array v {3, 1,	4, 1, 5, 9};
	    print("original array:  ", v);

	    std::ranges::make_heap(v);
	    print("after make_heap: ", v);

	    std::ranges::sort_heap(v);
	    print("after sort_heap: ", v);
	}

Output:
	original array:	 3 1 4 1 5 9
	after make_heap: 9 5 4 1 1 3
	after sort_heap: 1 1 3 4 5 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::make_heap	creates	a max heap out of a range of elements
	  (C++20)		(niebloid)
	  ranges::pop_heap	removes	the largest element from a max heap
	  (C++20)		(niebloid)
	  ranges::push_heap	adds an	element	to a max heap
	  (C++20)		(niebloid)
				turns a	max heap  into	a  range  of  elements
       sorted in ascending
	  sort_heap		order
				(function template)

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

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

home | help