Un max-heap este un arbore binar complet cu următoarea proprietate suplimentară: valoarea din orice nod este mai mare sau egală cu valorile din orice nod descendent.

Similar se definește noțiunea de min-heap: valoarea din orice nod este mai mică sau egală cu valorile descendenților.

Într-un max-heap rădăcina are valoare maximă, iar într-un min-heap rădăcina are valoare minimă. Nu se precizează nicio relație între valorile din fiii unui nod.

Următorul arbore binar complet este max-heap:

Pentru ca un arbore binar complet să fie max-heap (și similar pentru min-heap), fiecare nod din arbore trebuie:

să fie mai mare sau egal cu descendenții săi (dacă există)
să fie mai mic sau egal cu tatăl său (dacă există)

Să presupunem că un arbore binar complet H[] are proprietatea de max_heap, cu excepția unui nod k. Cum îl corectăm, astfel încât să devină max-heap?! Distingem două cazuri:

dacă nodul k este mai mare decât tatăl său (H[k] > H[k/2) îl vom muta în sus în arbore, până când acesta devine max-heap. Această operație se numește promovare a unui nod în heap;
dacă nodul k este mai mic decât cel puțin unul dintre fii săi (H[k] < H[2*k] și/sau H[k] < H[2*k+1]) îl vom muta în jos în mod convenabil, până când arborele devine max_heap. Această operație se numește cernere a unui nod în arbore.

Cerința

Se consideră o colecție de numere naturale, inițial vidă. Asupra ei se fac două tipuri de operații:

1 x – valoarea x se adaugă în colecție;
2 – cea mai mare valoare din colecție se afișează, apoi se elimină din colecție.

Dându-se un șir de m operații, să se afișeze în ordine rezultatele operațiilor de tip 2.

Date de intrare

Fișierul de intrare heap.in conține pe prima linie numărul m, iar pe următoarele m linii câte o operație.

Date de ieșire

Fișierul de ieșire heap.out va conține rezultatele operațiilor de tip 2, câte unul pe o linie, în ordinea în care au fost efectuate.

Restricții și precizări

1 ≤ m ≤ 250.000
1 ≤ x ≤ 1.000.000.000

Exemplu

heap.in

heap.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Heap:

#include <iostream>
#include <fstream>
using namespace std;

fstream fin, fout;

int H[250005], n , m , op, k;

void Promovare(int k)
{
    bool esteHeap = false;
    while(k > 1 && !  esteHeap)
    {
        if(H[k] <= H[k/2])
            esteHeap = 1;
        else
        {
            int aux = H[k]; H[k] = H[k/2] ; H[k/2] = aux;
            k /= 2;
        }
    }
}

void Cernere(int k)
{
    bool esteHeap = false;
    while(2 * k <= n && !esteHeap){
        int p = 2 * k;
        if(p + 1 <= n && H[p] < H[p+1])
            p ++;
        if(H[k] >= H[p])
            esteHeap = true;
        else
        {
            int aux = H[k]; H[k] = H[p]; H[p] = aux;
            k = p;
        }
        
    }
}

int main(){
    fin.open("heap.in", ios::in);
    fout.open("heap.out", ios::out);
    fin >> m;
    n = 0;
    for ( ; m ; m --)
    {
        fin >> op;
        if(op == 1)
        {
            fin >> k;
            H[++n] = k;
            Promovare(n);
        }
        else
        {
            fout << H[1] << "
";
            H[1] = H[n--];
            Cernere(1);
        }
    }
    fin.close() ,fout.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1855 Heap

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1855 Heap de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1855 Heap