std::ranges::push_heap(3)

📦 version 2024.07.05, in nixpkgs unstable, opensuse-leap 16.0

✨ std::ranges::push_heap ✨

Okay bestie, so this is literally the glow-up of heap insertion in C++20. It lives in the C++ Standard Library and it's giving main character energy for your priority queues.

💖 NAME 💖

std::ranges::push_heap — no cap, this is the function that adds a new element to your max heap and keeps everything sorted so you don't have to.

🌸 SYNOPSIS 🌸

So you're chilling in the <algorithm> header (iykyk), and here are the two call signatures that are gonna be your new besties:

template< std::random_access_iterator I, std::sentinel_for<I> S,
          class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
(1) (since C++20)
constexpr I
    push_heap( I first, S last, Comp comp = {}, Proj proj = {} );

template< ranges::random_access_range R, class Comp = ranges::less,
          class Proj = std::identity >
(2) (since C++20)
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R>
    push_heap( R&& r, Comp comp = {}, Proj proj = {} );

🎀 DESCRIPTION 🎀

Okay so picture this: you've got this max heap already set up in the range [first, last - 1), right? And there's this new element just vibing at the position last - 1. This function literally inserts that element into the heap so it's all proper and heapified again. It's like when you finally introduce your new friend to the group chat and they just fit in perfectly.

Here's the breakdown of the two versions:

Version (1) — Elements get compared using the binary comparison function comp and the projection object proj. Like, it's customizing how things get compared, you know?
Version (2) — Same energy as (1), but it uses r as the range, as if you're using ranges::begin(r) as first and ranges::end(r) as last. Super convenient, honestly.

Now, about the niebloids (the function-like entities on this page) — there's some technical tea you need to sip:

You cannot specify explicit template argument lists when calling any of them. Just don't even try.
None of them are visible to argument-dependent lookup. They're lowkey hiding.
When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited. Yeah, it's a whole thing.

In practice, they might be implemented as function objects or with special compiler extensions. Either way, they work.

💅 PARAMETERS 💅

Okay so these are the parameters, and they're all super important:

first, last — the range of elements defining the heap you wanna modify. This is your starting point, bestie.
r — the range of elements defining the heap you wanna modify. Same energy, just a range instead of iterators.
pred — the predicate to apply to the projected elements. This is how you decide what goes where.
proj — the projection to apply to the elements. This transforms your elements before comparison.

🦋 RETURN VALUE 🦋

An iterator equal to last. That's it. That's the return value. It's literally just telling you where the end is. Iconic.

🔥 COMPLEXITY 🔥

Okay so given N = ranges::distance(first, last), this function does at most (\log(N)) comparisons and (2\log(N)) projections. Ngl, that's pretty efficient. Logarithmic time, slay.

🌈 NOTES 🌈

So a max heap is a range of elements [f, l), arranged with respect to comparator comp and projection proj, and it has these three properties that you need to know about:

With N = l - f, p = f[(i - 1) / 2], and q = f[i], for all 0 < i < N, the expression std::invoke(comp, std::invoke(proj, p), std::invoke(proj, q)) evaluates to false. (Basically, the parent is never less than the child under the comparator. That's the whole heap property.)
A new element can be added using ranges::push_heap, in (\mathcal{O}(\log N)) time. That's literally what we're talking about here.
The first element can be removed using ranges::pop_heap, in (\mathcal{O}(\log N)) time. Just so you know what's up.

🧚 POSSIBLE IMPLEMENTATION 🧚

If you're curious how this is actually implemented (or you wanna copy it for your own project), here's the possible implementation. It's literally the blueprint of the whole thing:

struct push_heap_fn {
    template<std::random_access_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr I
        operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        const auto n{ranges::distance(first, last)};
        const auto length{n};
        if (n > 1)
        {
            I last{first + n};
            n = (n - 2) / 2;
            I i{first + n};
            if (std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *--last)))
            {
                std::iter_value_t<I> v {ranges::iter_move(last)};
                do
                {
                    *last = ranges::iter_move(i);
                    last = i;
                    if (n == 0)
                        break;
                    n = (n - 1) / 2;
                    i = first + n;
                }
                while (std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, v)));
                *last = std::move(v);
            }
        }
        return first + length;
    }

    template<ranges::random_access_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj));
    } };

inline constexpr push_heap_fn push_heap {};

⭐ EXAMPLE ⭐

Okay bestie, here's a full-on example that you can literally run. It shows you how to use push_heap in the wild:

// Run this code

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

void out(const auto& what, int n = 1)
{
    while (n-- > 0)
        std::cout << what;
}

void print(auto rem, auto const& v)
{
    out(rem);
    for (auto e : v)
        out(e), out(' ');
    out('\n');
}

void draw_heap(auto const& v)
{
    auto bails = [](int n, int w)
    {
        auto b = [](int w) { out("┌"), out("─", w), out("┴"), out("─", w), out("┐"); };
        if (!(n /= 2))
            return;
        for (out(' ', w); n-- > 0;)
            b(w), out(' ', w + w + 1);
        out('\n');
    };
    auto data = [](int n, int w, auto& first, auto last)
    {
        for (out(' ', w); n-- > 0 && first != last; ++first)
            out(*first), out(' ', w + w + 1);
        out('\n');
    };
    auto tier = [&](int t, int m, auto& first, auto last)
    {
        const int n{1 << t};
        const int w{(1 << (m - t - 1)) - 1};
        bails(n, w), data(n, w, first, last);
    };
    const int m{static_cast<int>(std::ceil(std::log2(1 + v.size())))};
    auto first{v.cbegin()};
    for (int i{}; i != m; ++i)
        tier(i, m, first, v.cend());
}

int main()
{
    std::vector<int> v{1, 6, 1, 8, 0, 3,};
    print("source vector v: ", v);

    std::ranges::make_heap(v);
    print("after make_heap: ", v);
    draw_heap(v);

    v.push_back(9);

    print("before push_heap: ", v);
    draw_heap(v);

    std::ranges::push_heap(v);
    print("after push_heap: ", v);
    draw_heap(v);
}

And here's the output. Look at how pretty the heap diagrams are:

source vector v: 1 6 1 8 0 3
after make_heap: 8 6 3 1 0 1
   8
 ┌─┴─┐
 6   3
┌┴┐ ┌┴┐
1 0 1
before push_heap: 8 6 3 1 0 1 9
   8
 ┌─┴─┐
 6   3
┌┴┐ ┌┴┐
1 0 1 9
after push_heap: 9 6 8 1 0 1 3
   9
 ┌─┴─┐
 6   8
┌┴┐ ┌┴┐
1 0 1 3

See how after push_heap, the 9 just slides into the top spot like it owns the place? That's the magic, bestie. 💅

👑 SEE ALSO 👑

You might also wanna check out these other heap-related functions, because they're all in the same friend group:

ranges::is_heap (C++20, niebloid) — checks if the given range is a max heap.
ranges::is_heap_until (C++20, niebloid) — finds the largest subrange that is a max heap.
ranges::make_heap (C++20, niebloid) — creates a max heap out of a range of elements.
ranges::pop_heap (C++20, niebloid) — removes the largest element from a max heap.
ranges::sort_heap (C++20, niebloid) — turns a max heap into a range of elements sorted in ascending order.
push_heap (function template) — adds an element to a max heap.

And that's the whole vibe, bestie! This page was brought to you by cppreference.com, rolled out on 2024.06.10, for std::ranges::push_heap(3). Go forth and heapify. Periodt. 🫶🎀

📦 where this page comes from

nixpkgs unstable: stdman 2024.07.05
opensuse-leap 16.0: stdman 2024.07.05-bp160.1.9 · MIT
💖 girlified by deepseek-ai/DeepSeek-V4.1-Flash-1017 on 2026-11-04: a language model's rewrite of the original, under its terms