Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

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.

Izvori