Laborator-5-Heap.txt

#include <iostream>

using namespace std;

void swap(int &a, int &b)
{
    int aux = a;
    a = b;
    b = aux;
}
class Heap
{
    int v[100];
    int n ; //numarul de noduri
    void pushUp(int k);
    void pushDown(int k);
public:
    Heap()
    {
        n = 0;
    };
    Heap(int v2[], int n2); //construieste un heap pe baza vectorului v2
    void insert(int); //adauga la final un element nou si ii face push up
    int delHead(); //returneaza si radacina dupa ce o sterge
    void sort(); //heapSort
    void print();
};

void Heap::pushUp(int k)
{
    while( k != 1 && v[k] > v[k/2]) //cat timp fiul este mai mare decat parintele, le interschimba
    {
        swap(v[k], v[k/2]);
        k = k/2;
    }
}

void Heap::insert(int val)
{
    n++;
    v[n] = val;
    pushUp(n);
}

void Heap::print()
{
    for(int i = 1; i <= n; i++)
        cout << v[i] << " ";
    cout<<endl;
}

void Heap::pushDown(int k)
{
    int maxim = k;
    if(v[maxim] < v[2*k] && 2*k <= n) //compar cu fiul stang
        maxim = 2*k;
    if(v[2*k+1] > v[maxim] && 2*k+1 <= n) //compar cu fiul drept
        maxim = 2*k+1;
    if(maxim != k)
    {
        swap(v[k], v[maxim]); //interschimb cu maximul dintre fii
        pushDown(maxim);
    }
}

Heap::Heap(int v2[], int n2)
{
    for(int i = 1; i <= n2; i++)
        v[i] = v2[i];
    for(int i = n/2; i >= 1; i++) //de la primul nod care nu e frunza, apelez pushDown
        pushDown(i);
}

int Heap::delHead()
{
    swap(v[1], v[n]);
    n--;
    pushDown(1);
    return v[n+1];
}

void Heap::sort()
{
    int nAux = n;
    for(int i = 1; i<= nAux; i++)
        delHead();
    n = nAux;
}

int main()
{

    Heap h;
    h.insert(3);
    h.insert(4);
    h.insert(11);
    h.insert(2);
    h.insert(5);
    h.insert(9);
    h.print();
    h.sort();
    h.print();


    int v2[100], n2;
    cout<<"n2 = ";
    cin>>n2;
    for(int i = 1; i<= n2; i++)
        cin>>v2[i];
    Heap h2(v2, n2);
    h2.print();


    return 0;
}