Defined in header
template<classRandomIt>voidmake_heap(RandomItfirst,RandomItlast); (1) (constexpr since C++20)template<classRandomIt,classCompare>voidmake_heap(RandomItfirst,RandomItlast,Comparecomp); (2) (constexpr since C++20)Constructs a
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 undefined:
Parameters
first, last - the pair of iterators defining the
of elements to make the binary heap range comp - comparison function object (i.e. an object that satisfies the requirements of
) which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:
boolcmp(constType1&a,constType2&b);
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 regardless of
(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 converted to both of them.
Type requirements -RandomIt must meet the requirements of
. -Compare must meet the requirements of
. Complexity
Given N as std::distance(first,last):
1) At most 3N comparisons using operator<(until C++20)std::less{}(since C++20).
2) At most 3N applications of the comparison function comp.
Example
Run this code
#include<algorithm>#include<functional>#include<iostream>#include<string_view>#include<vector>voidprint(std::string_viewtext,conststd::vector<int>&v={}){std::cout<<text<<": ";for(constauto&e:v)std::cout<<e<<' ';std::cout<<'\n';}intmain(){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);autotop=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);autotop1=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 retroactively to previously published C++ standards.
DR Applied to Behavior as published Correct behavior
C++98 the elements of [first, last) was not required to be swappable required See also
(C++11)
checks if the given range is a max heap
(function template & algorithm function object)
(C++20)
(C++11)
finds the largest subrange that is a max heap
(function template & algorithm function object)
(C++20)
adds an element to a max heap
(function template & algorithm function object)
(C++20)
removes the largest element from a max heap
(function template & algorithm function object)
(C++20)
turns a max heap into a range of elements sorted in ascending order
(function template & algorithm function object)
(C++20)
adapts a container to provide priority queue
(class template)
(C++20)
creates a max heap out of a range of elements
(algorithm function object)