KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::make_heap — een heap maken van een bereik

std::make_heap herschikt een bereik in lineaire tijd tot een heap. Standaard komt het grootste element vooraan; met een aangepaste comparator kun je een min-heap maken. Er is geen garantie dat het resulterende bereik gesorteerd is.

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

Syntax

#include <algorithm>

namespace std {

template<class RandomAccessIterator>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

} // namespace std

std::make_heap, gedeclareerd in <algorithm>, zet [first, last) om in een heap, herschikt de elementen en retourneert void. Het bereik hoeft nog geen heap te zijn. De standaardvergelijking maakt een max-heap: bij een niet-leeg bereik is *first het grootste element. Dit sorteert niet het hele bereik; de exacte volgorde van de overige elementen is niet gespecificeerd.

De overload met comp maakt een heap volgens die comparator. Voor elk kind moet comp(parent, child) false zijn. std::greater<int>{} uit <functional> levert een min-heap op. De comparator moet een strikte zwakke ordening definiëren; gebruik geen <= in plaats van <.

Random-access-iterators zijn vereist en de elementen moeten verwisseld, met move-constructie gemaakt en met move-toewijzing toegewezen kunnen worden. Voor N = last - first voert het algoritme hoogstens 3 * N vergelijkingen uit; de vergelijkingscomplexiteit is dus lineair. Een leeg bereik is geldig, maar lees dan niet *first of front().

Het voorbeeld controleert de wortel en de heap-eigenschap, in plaats van een bepaalde indeling van alle elementen aan te nemen. Gebruik bij volgende bewerkingen dezelfde ordening: std::push_heap, std::pop_heap en std::sort_heap moeten een compatibele comparator gebruiken. std::pop_heap verwijdert op zichzelf geen element uit de container.

Voorbeelden

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

int main() {
    std::vector<int> values{4, 1, 7, 3, 2};

    std::make_heap(values.begin(), values.end());
    std::cout << "max: " << values.front() << '\n';
    std::cout << std::boolalpha
              << "heap: " << std::is_heap(values.begin(), values.end()) << '\n';

    std::make_heap(values.begin(), values.end(), std::greater<int>{});
    std::cout << "min: " << values.front() << '\n';
}

Resultaat

max: 7
heap: true
min: 1

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