std::ranges:: push_heap

Insère le dernier élément de la plage spécifiée dans un tas par rapport à comp et proj , où le tas est constitué de tous les éléments de la plage sauf le dernier. Le tas après l'insertion constituera l'ensemble de la plage.

Si la plage spécifiée (à l'exclusion du dernier élément) n'est pas un tas par rapport à comp et proj , le comportement est indéfini.

Les entités de type fonction décrites sur cette page sont des objets fonction algorithme (informellement appelés niebloids ), c'est-à-dire :

• Les listes d'arguments de template explicites ne peuvent pas être spécifiées lors de l'appel de l'une d'entre elles.
• Aucune d'entre elles n'est visible pour la recherche dépendante des arguments .
• Lorsque l'une d'entre elles est trouvée par la recherche non qualifiée normale comme nom à gauche de l'opérateur d'appel de fonction, la recherche dépendante des arguments est inhibée.

Paramètres

Valeur de retour

Complexité

Au plus \(\scriptsize \log{(N)}\) log(N) applications de comp et \(\scriptsize 2\log{(N)}\) 2log(N) applications de proj , où \(\scriptsize N \) N est :

Implémentation possible

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{};

Exemple

#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);
}

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

Voir aussi