KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::push_heap — een element aan een heap toevoegen

std::push_heap herstelt de heap-eigenschap nadat één element aan het einde van een bereik is toegevoegd. De container wordt er niet groter door: het nieuwe element moet al op last - 1 staan en het voorafgaande deel van het bereik moet een geldige heap zijn.

Versie: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>

std::push_heap(first, last);
std::push_heap(first, last, comp);

std::push_heap, gedeclareerd in <algorithm>, neemt het element op last - 1 op in de heap over [first, last). De functie voegt zelf geen element aan de container toe en retourneert void. De gebruikelijke volgorde is push_back, gevolgd door std::push_heap met de actuele iterators.

Vóór de aanroep moet [first, last - 1) al een heap zijn volgens dezelfde ordening. Het bereik moet ten minste het nieuwe element bevatten; roep het algoritme niet aan voor een leeg bereik. Gebruik std::make_heap om van willekeurige gegevens een heap te maken, niet één enkele aanroep van std::push_heap.

De standaardvergelijking maakt een max-heap: het grootste element staat vooraan. De overload met comp verandert de ordening; std::greater<int>{} maakt een min-heap. De comparator moet een strikte zwakke ordening definiëren en overeenkomen met de ordening van de bestaande heap. Een heap hoeft niet gesorteerd te zijn.

Iterators met willekeurige toegang zijn vereist, evenals elementen die verwisselen, move-constructie en move-toewijzing ondersteunen. Het aantal vergelijkingen is O(log N), waarbij N = last - first; de kosten van de voorafgaande push_back komen daar afzonderlijk bij. In het voorbeeld is {9, 5, 7} al een heap. Na het toevoegen van 12 is dus één aanroep voldoende om de heap-eigenschap te herstellen.

Voorbeelden

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

int main() {
    std::vector<int> heap{9, 5, 7};
    heap.push_back(12);
    std::push_heap(heap.begin(), heap.end());

    std::cout << "top: " << heap.front() << '\n';
    std::cout << "size: " << heap.size() << '\n';
    std::cout << "is_heap: " << std::boolalpha
              << std::is_heap(heap.begin(), heap.end()) << '\n';
}

Resultaat

top: 12
size: 4
is_heap: true

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen