# std::make_heap

> C++ Atlas: `cppatlas.com/w/cpp/algorithm/make_heap` | Source: https://en.cppreference.com/w/cpp/algorithm/make_heap | Domain: Algorithms | Standards: C++11, C++20

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

## Official Specification Summary (cppreference)

```cpp
// 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:

(until C++11):

- The type of `*first` is not *Swappable*.

(since C++11):

- `RandomIt` is not *ValueSwappable*.
- The type of `*first` is not *MoveConstructible*.
- The type of `*first` is not *MoveAssignable*.

### Parameters

- `first, last` - the range to make the heap from
- `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:

  `bool cmp(const Type1& a, const Type2& 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 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

```cpp
#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:

```text
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 |

### See also

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

---
Attribution: content from https://en.cppreference.com/w/cpp/algorithm/make_heap (cppreference.com), licensed under CC-BY-SA 3.0 and GFDL. Modified: converted to markdown, study notes added. Offline snapshot of 9 February 2025.