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 stdstd::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.