std::make_heap

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

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 undefined:

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

Parameters

first, last	-	the pair of iterators defining the range of elements to make the binary heap range
comp	-	comparison function object (i.e. an object that satisfies 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: 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 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 converted 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 function comp.

Example

#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 retroactively 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 to be swappable	required

is_heap (C++11)	checks if the given range is a max heap (function template & algorithm function object)
ranges::is_heap (C++20)
is_heap_until (C++11)	finds the largest subrange that is a max heap (function template & algorithm function object)
ranges::is_heap_until (C++20)
push_heap	adds an element to a max heap (function template & algorithm function object)
ranges::push_heap (C++20)
pop_heap	removes the largest element from a max heap (function template & algorithm function object)
ranges::pop_heap (C++20)
sort_heap	turns a max heap into a range of elements sorted in ascending order (function template & algorithm function object)
ranges::sort_heap (C++20)
priority_queue	adapts a container to provide priority queue (class template)
ranges::make_heap (C++20)	creates a max heap out of a range of elements (algorithm function object)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/make_heap

std::make_heap

Parameters

Complexity

Example

Defect reports

See also