std::make_heap() algorithm
- od C++20
- do C++20
// (1)
template< class RandomIt >
constexpr void make_heap( RandomIt first, RandomIt last );
// (2)
template< class RandomIt, class Compare >
constexpr void make_heap( RandomIt first, RandomIt last, Compare comp );
// (1)
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );
// (2)
template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp );
Checks whether the elements in range [first
; last
) are a max heap.
-
(1) Elements are compared using
operator<
. -
(2) Elements are compared using the given binary comparison function
comp
.
Parameters
first last | The range of elements to make a heap from. |
policy | The execution policy to use. See execution policy for details. |
comp | Comparison function object (i.e. an object that satisfies the requirements of Compare). The signature of the comparison function should be equivalent to the following:
|
Type requirements
RandomIt | LegacyRandomAccessIterator |
The type defereferenced RandomIt | MoveAssignable MoveConstructible |
Return value
(none)
Complexity
At most 3 * std::distance(first, last)
comparisons.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Notes
A max heap is a range of elements [f
; l
) that has the following properties:
- Given
N
asl - f
, for all0 < i < N
,f[(i - 1) / 2]
does not compare less thanf[i]
. - A new element can be added using
std::push_heap
, in O(log(N)) time. - The first element can be removed using
std::pop_heap
, in O(log(N)) time.
Examples
#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <vector>
void print(std::string_view text, std::vector<int> const& 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);
}
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
Hover to see the original license.