std::ranges::pop_heap

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 pop_heap( I first, S last, Comp comp = {}, Proj proj = {} );

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>
    pop_heap( R&& r, Comp comp = {}, Proj proj = {} );

Vertauscht das erste Element und das letzte Element des angegebenen Heaps in Bezug auf comp und proj und macht den Teilbereich mit Ausnahme der ersten Position zu einem Heap in Bezug auf comp und proj. Dies hat den Effekt, das erste Element aus dem angegebenen Heap zu entfernen.

Die funktionsähnlichen Entitäten, die auf dieser Seite beschrieben werden, sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), d.h.:

• Explizite Vorlagenargumentlisten können nicht angegeben werden, wenn eines von ihnen aufgerufen wird.
• Keines von ihnen ist für argumentabhängige Suche sichtbar.
• Wenn eines von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird argumentabhängige Suche unterdrückt.

Parameter

Rückgabewert

Komplexität

Höchstens \(\scriptsize 2\log{(N)}\) 2log(N) Anwendungen von comp und \(\scriptsize 4\log{(N)}\) 4log(N) Anwendungen von proj , wobei \(\scriptsize N \) N ist:

Beispiel

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <string_view>
template<class I = int*>
void print(std::string_view rem, I first = {}, I last = {},
           std::string_view term = "\n")
{
    for (std::cout << rem; first != last; ++first)
        std::cout << *first << ' ';
    std::cout << term;
}
int main()
{
    std::array v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    print("initially, v: ", v.cbegin(), v.cend());
    std::ranges::make_heap(v);
    print("make_heap, v: ", v.cbegin(), v.cend());
    print("convert heap into sorted array:");
    for (auto n {std::ssize(v)}; n >= 0; --n)
    {
        std::ranges::pop_heap(v.begin(), v.begin() + n);
        print("[ ", v.cbegin(), v.cbegin() + n, "]  ");
        print("[ ", v.cbegin() + n, v.cend(), "]\n");
    }
}

initially, v: 3 1 4 1 5 9 2 6 5 3
make_heap, v: 9 6 4 5 5 3 2 1 1 3
convert heap into sorted array:
[ 6 5 4 3 5 3 2 1 1 9 ]  [ ]
[ 5 5 4 3 1 3 2 1 6 ]  [ 9 ]
[ 5 3 4 1 1 3 2 5 ]  [ 6 9 ]
[ 4 3 3 1 1 2 5 ]  [ 5 6 9 ]
[ 3 2 3 1 1 4 ]  [ 5 5 6 9 ]
[ 3 2 1 1 3 ]  [ 4 5 5 6 9 ]
[ 2 1 1 3 ]  [ 3 4 5 5 6 9 ]
[ 1 1 2 ]  [ 3 3 4 5 5 6 9 ]
[ 1 1 ]  [ 2 3 3 4 5 5 6 9 ]
[ 1 ]  [ 1 2 3 3 4 5 5 6 9 ]
[ ]  [ 1 1 2 3 3 4 5 5 6 9 ]

Siehe auch