CKTIS / C++
std::push_heap — dodavanje elementa u hrpu
std::push_heap obnavlja svojstvo hrpe nakon što je jedan element dodan na kraj raspona. Ne povećava veličinu spremnika: novi element već mora biti na mjestu last - 1, a prethodni dio raspona mora biti valjana hrpa.
Verzija: C++23; repository compiler flag, production runtime not attested
Sintaksa
#include <algorithm>
std::push_heap(first, last);
std::push_heap(first, last, comp);std::push_heap iz zaglavlja <algorithm> uključuje element na mjestu last - 1 u hrpu koja obuhvaća [first, last). Sam ne dodaje element u spremnik i vraća void. Uobičajen je slijed pozvati push_back, a zatim std::push_heap s aktualnim iteratorima.
Prije poziva [first, last - 1) već mora biti hrpa prema istom poretku. Raspon mora sadržavati barem novi element; algoritam nemojte pozivati za prazan raspon. Za izgradnju hrpe iz proizvoljnih podataka upotrijebite std::make_heap, a ne jedan poziv std::push_heap.
Zadana usporedba stvara maksimalnu hrpu: najveći je element na početku. Preopterećenje koje prima comp mijenja poredak; std::greater<int>{} stvara minimalnu hrpu. Usporednik mora definirati strogi slabi poredak i odgovarati poretku postojeće hrpe. Hrpa ne mora biti sortirana.
Potrebni su iteratori s nasumičnim pristupom i elementi koji podržavaju zamjenu, konstrukciju premještanjem i dodjelu premještanjem. Broj usporedbi je O(log N), gdje je N = last - first; trošak prethodnog push_back zaseban je. U primjeru je {9, 5, 7} već hrpa, pa je nakon dodavanja 12 dovoljan jedan poziv za obnovu svojstva hrpe.
Primjeri
#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';
}
Rezultat
top: 12 size: 4 is_heap: true
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.