std::ranges::push_heap
Von cppreference.com
| Definiert in Header <algorithm> |
||
| Aufruf-Signatur |
||
| template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > |
(1) | (seit C++20) |
| template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > |
(2) | (seit C++20) |
Fügt das letzte Element des angegebenen Bereichs in einen Heap ein, bezüglich comp und proj, wobei der Heap aus allen Elementen des Bereichs außer dem letzten besteht. Der Heap nach der Einfügung ist der gesamte Bereich.
1) Der angegebene Bereich ist
[first, last).2) Der angegebene Bereich ist r.
Wenn der angegebene Bereich (ohne das letzte Element) kein Heap bezüglich comp und proj ist, ist das Verhalten undefiniert.
Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als niebloids bekannt), d.h.
- Können explizite Template-Argumentlisten bei keinem von ihnen angegeben werden.
- Keiner von ihnen ist für Argument-abhängige Suche sichtbar.
- Wenn einer von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die Argument-abhängige Suche unterdrückt.
Inhalt |
[bearbeiten] Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den zu modifizierenden Bereich definiert |
| r | - | Der Bereich der zu ändernden Elemente |
| comp | - | Comparator, der auf die projizierten Elemente angewendet werden soll |
| proj | - | Projektion, die auf die Elemente angewendet wird |
[bearbeiten] Rückgabewert
1) last
2) ranges::end(r)
[bearbeiten] Komplexität
Höchstens log(N) Anwendungen von comp und 2log(N) Anwendungen von proj, wobei N die Größe des Bereichs ist.
1) ranges::distance(first, last)
2) ranges::distance(r)
[bearbeiten] Mögliche Implementierung
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{}; |
[bearbeiten] Beispiel
Führen Sie diesen Code aus
#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); }
Ausgabe
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
[bearbeiten] Siehe auch
| (C++20) |
Prüft, ob der gegebene Bereich ein Max-Heap ist (Algorithmus-Funktionsobjekt) |
| (C++20) |
Findet den größten Teilbereich, der ein Max-Heap ist (Algorithmus-Funktionsobjekt) |
| (C++20) |
Erstellt aus einem Bereich von Elementen einen Max-Heap (Algorithmus-Funktionsobjekt) |
| (C++20) |
Entfernt das größte Element aus einem Max-Heap (Algorithmus-Funktionsobjekt) |
| (C++20) |
Verwandelt einen Max-Heap in einen aufsteigend sortierten Bereich von Elementen (Algorithmus-Funktionsobjekt) |
| Fügt ein Element zu einem Max-Heap hinzu (Funktionstemplate) |
