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

FreeBSD Manual Pages

  
 
  

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

NAME
       std::sort_heap -	std::sort_heap

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

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

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

Parameters
	  first, last -	 the range of elements to sort
			 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 2Nlog(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.

Possible implementation
First version
	  template< class RandomIt >
	  void sort_heap( RandomIt first, RandomIt last	)
	  {
	      while (first != last)
		  std::pop_heap(first, last--);
	  }

Second version
	  template< class RandomIt, class Compare >
	  void sort_heap( RandomIt first, RandomIt last, Compare comp )
	  {
	      while (first != last)
		  std::pop_heap(first, last--, comp);
	  }

Example
       // Run this code

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

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

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

	    std::cout << "heap:\t";
	    for	(const auto &i : v) {
		std::cout << i << ' ';
	    }

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

	    std::cout << "\nsorted:\t";
	    for	(const auto &i : v) {
		std::cout << i << ' ';
	    }
	    std::cout << '\n';
	}

Output:
	heap:	9 4 5 1	1 3
	sorted:	1 1 3 4	5 9

	 Defect	reports

	  The following	behavior-changing defect reports were applied retroac-
       tively to
	  previously published C++ standards.

	     DR	     Applied	to		   Behavior    as    published
       Correct behavior
	  LWG  2444 C++98      complexity requirement was wrong	by a factor of
       corrected
			      2

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

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

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

home | help