`std::make_heap` în C++

Transformă un vector într-un heap (cel mai mare element mereu primul) și îl întreține cu push_heap, pop_heap, sort_heap.

Sintaxă

void make_heap(RandomIt first, RandomIt last);
void push_heap(RandomIt first, RandomIt last);
void pop_heap(RandomIt first, RandomIt last);
void sort_heap(RandomIt first, RandomIt last);

Ce face `std::make_heap`

Un heap (ansamblu) este un vector aranjat astfel încât v.front() este mereu elementul maxim. std::make_heap creează această aranjare în timp liniar. Restul elementelor nu sunt sortate, doar organizate ca un arbore.

După ce adaugi un element cu push_back, apelezi std::push_heap ca să-l duci la locul lui. std::pop_heap mută maximul la finalul vectorului (apoi îl scoți cu pop_back). std::sort_heap transformă heap-ul într-un vector sortat crescător. Toate operațiile sunt O(log n), cu excepția sortării, care este O(n log n).

std::priority_queue face exact asta în spate; funcțiile acestea sunt utile când vrei acces și la restul vectorului.

Parametri

Parametru	Descriere
`first, last`	Intervalul care este (sau devine) heap.
`comp`	Opțional. Cu `std::greater<>()` obții un heap de minim.

Ce returnează

Nimic.

Exemple

Exemplul 1: Ciclul complet

#include <algorithm>
#include <print>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 4, 1, 5, 9, 2};

    std::make_heap(v.begin(), v.end());
    std::println("Maximul: {}", v.front());

    v.push_back(7);
    std::push_heap(v.begin(), v.end());
    std::println("După adăugarea lui 7, maximul: {}", v.front());

    std::pop_heap(v.begin(), v.end());
    std::println("Scos: {}", v.back());
    v.pop_back();
    std::println("Noul maxim: {}", v.front());

    std::sort_heap(v.begin(), v.end());
    std::println("Sortat: {}", v);
}

Rezultat

Maximul: 9
După adăugarea lui 7, maximul: 9
Scos: 9
Noul maxim: 7
Sortat: [1, 1, 2, 3, 4, 5, 7]

Exemplul 2: Coadă de urgențe (heap de minim)

Cu std::greater<>() în toate apelurile, pe primul loc stă prioritatea cea mai mică (1 = cea mai urgentă). Perechile se compară întâi după prioritate, apoi după text, de aceea „Fractură” iese înaintea lui „Infarct”.

#include <algorithm>
#include <functional>
#include <print>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::vector<std::pair<int, std::string>> urgente{{3, "Gripă"}, {1, "Fractură"}, {2, "Arsură"}};
    std::make_heap(urgente.begin(), urgente.end(), std::greater<>());

    urgente.push_back({1, "Infarct"});
    std::push_heap(urgente.begin(), urgente.end(), std::greater<>());

    while (!urgente.empty()) {
        std::pop_heap(urgente.begin(), urgente.end(), std::greater<>());
        auto [prioritate, caz] = urgente.back();
        urgente.pop_back();
        std::println("{} (prioritate {})", caz, prioritate);
    }
}