CKTIS / C++
std::make_heap — building a heap from a range
std::make_heap rearranges a range into a heap in linear time. By default, the largest element moves to the front; a custom comparator can create a min-heap. The resulting range is not guaranteed to be sorted.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
namespace std {
template<class RandomAccessIterator>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
} // namespace stdstd::make_heap, declared in <algorithm>, transforms [first, last) into a heap, rearranging its elements and returning void. The range need not already be a heap. The default comparison creates a max-heap: for a nonempty range, *first is the largest element. This does not sort the entire range; the exact arrangement of the other elements is unspecified.
The overload taking comp builds a heap according to that comparator. For each child, comp(parent, child) must be false. std::greater<int>{} from <functional> produces a min-heap. The comparator must define a strict weak ordering; do not use <= instead of <.
Random-access iterators are required, and the elements must support swapping, move construction, and move assignment. For N = last - first, the algorithm performs at most 3 * N comparisons, giving linear comparison complexity. An empty range is valid, but you must not then read *first or front().
The example checks the root and heap property rather than assuming a particular arrangement of all elements. Preserve the same ordering in subsequent operations: std::push_heap, std::pop_heap, and std::sort_heap must use a compatible comparator. std::pop_heap alone does not remove an element from the container.
Examples
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{4, 1, 7, 3, 2};
std::make_heap(values.begin(), values.end());
std::cout << "max: " << values.front() << '\n';
std::cout << std::boolalpha
<< "heap: " << std::is_heap(values.begin(), values.end()) << '\n';
std::make_heap(values.begin(), values.end(), std::greater<int>{});
std::cout << "min: " << values.front() << '\n';
}Result
max: 7 heap: true min: 1
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.