std::ranges::push_heap
| Definiert in Header <algorithm>
|
||
| Aufrufsignatur |
||
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 push_heap( I first, S last, Comp comp = {}, Proj proj = {} );
|
(1) | (seit C++20) |
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>
push_heap( R&& r, Comp comp = {}, Proj proj = {} );
|
(2) | (seit C++20) |
Fügt das letzte Element im angegebenen Bereich in einen Heap bezüglich comp und proj ein, wobei der Heap aus allen Elementen des Bereichs außer dem letzten besteht. Der Heap nach dem Einfügen ist der gesamte Bereich.
[first, last).r.Wenn der angegebene Bereich (ohne das letzte Element) bezüglich comp und proj kein Heap ist, ist das Verhalten undefiniert.
Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), das heißt:
- Explizite Vorlagenargumentlisten können beim Aufruf einer von ihnen nicht angegeben werden.
- Keine von ihnen ist für argumentabhängige Namenssuche sichtbar.
- Wenn eine von ihnen durch normale unqualifizierte Namenssuche als Name links vom Funktionsaufrufoperator gefunden wird, wird argumentabhängige Namenssuche unterdrückt.
Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den Bereich der zu ändernden Elemente definiert |
| r | - |
der
range
der zu ändernden Elemente
|
| comp | - | Komparator, der auf die projizierten Elemente angewendet wird |
| proj | - | Projektion, die auf die Elemente angewendet wird |
Rückgabewert
Komplexität
Höchstens log(N) Anwendungen von comp und 2log(N) Anwendungen von proj , wobei N ist:
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{}; |
Beispiel
#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
Siehe auch
(C++20) |
prüft, ob der angegebene Bereich ein Max-Heap ist (Algorithmus-Funktionsobjekt) |
(C++20) |
findet den größten Teilbereich, der ein Max-Heap ist (Algorithmus-Funktionsobjekt) |
(C++20) |
erzeugt einen Max-Heap aus einem Bereich von Elementen (Algorithmus-Funktionsobjekt) |
(C++20) |
entfernt das größte Element aus einem Max-Heap (Algorithmus-Funktionsobjekt) |
(C++20) |
wandelt einen Max-Heap in einen sortierten Bereich von Elementen um (Algorithmus-Funktionsobjekt) |
| fügt einem Max-Heap ein Element hinzu (Funktionsschablone) |