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 >				   (1) (const-
       expr since C++20)
	  void make_heap( RandomIt first, RandomIt last	);
	  template< class RandomIt, class Compare >
	  void make_heap( RandomIt first, RandomIt last, Compare   (2) (const-
       expr since C++20)
	  comp );

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

	  1) The constructed heap is with respect to
	  operator<
	  (until C++20)
	  std::less{}
	  (since C++20).
	  2) The constructed heap is with respect to comp.

	  If any of the	following conditions is	satisfied, the behavior	is un-
       defined:

	    * The type of *first is not	Swappable.	     (until C++11)
	    * RandomIt is not ValueSwappable.
	    * The type of *first is not	MoveConstructible.   (since C++11)
	    * The type of *first is not	MoveAssignable.

Parameters
	  first, last -	 the range 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.
	  -
	  Compare must meet the	requirements of	Compare.

Complexity
	  Given	\(\scriptsize N\)N as std::distance(first, last):

	  1) At	most \(\scriptsize 3N\)3N comparisons using
	  operator<
	  (until C++20)
	  std::less{}
	  (since C++20).
	  2) At	most \(\scriptsize 3N\)3N applications of the comparison func-
       tion comp.

Example
       // Run this code

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

	void print(std::string_view text, const	std::vector<int>& 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

	  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 3032 C++98      the elements of [first, last) was	 not  required
       required
			      to be swappable

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		  2024.06.10		     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.1.quarterly>

home | help