kopiec

// Lab06KopiecBinarny.cpp : Ten plik zawiera funkcję „main”. W nim rozpoczyna się i kończy wykonywanie programu.
//

#include <iostream>
#include <random>

using namespace std;

struct Kopiec
{
public:
    int* dane;
    int rozmiar_max;
    int rozmiar;

    Kopiec()
    {
        rozmiar = 0;
        rozmiar_max = 1;
        dane = new int[rozmiar_max];
    }

    void Dodaj(int key);
    void Kopcowanie(int key);
    void zamien(int* x, int* y);
    int rodzic(int indeks);
    int l_dziecko(int indeks);
    int p_dziecko(int indeks);
    void Kopcowanie_dol(int i);
    void usun();
};

void Kopiec::Dodaj(int key)
{
    if (rozmiar < rozmiar_max)
    {
        dane[rozmiar] = key;
        rozmiar += 1;
    }
    else
    {
        rozmiar_max = rozmiar_max + 1;
        int* tab = new int[rozmiar_max];
        for (int i = 0; i < rozmiar_max; i++)
        {
            tab[i] = dane[i];
        }
        tab[rozmiar] = key;
        rozmiar += 1;
        delete[] dane;
        dane = tab;
    }

    Kopcowanie(key);
}

void Kopiec::Kopcowanie(int key)
{
    int i = rozmiar - 1;
    dane[i] = key;

    while( i != 0 && dane[rodzic(i)] < dane[i])
    {
        zamien(&dane[i], &dane[rodzic(i)]);
        i = rodzic(i);
    }

}

void Kopiec::zamien(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;

}


void Kopiec::Kopcowanie_dol(int i)
{
    int l = l_dziecko(i);
    int r = p_dziecko(i);
    int smallest = i;
    if (l < rozmiar && dane[l] > dane[i])
        smallest = l;
    if (r < rozmiar && dane[r] > dane[smallest])
        smallest = r;
    if (smallest != i)
    {
        zamien(&dane[i], &dane[smallest]);
        Kopcowanie_dol(smallest);
    }
}

void Kopiec::usun()
{
    int* tab = new int[rozmiar - 1];
    zamien(&dane[0], &dane[rozmiar - 1]);
    for (int i = 0; i < rozmiar - 1; i++)
    {
        tab[i] = dane[i];
    }
    delete[] dane;
    dane = tab;
    Kopcowanie_dol(0);
}


int Kopiec::rodzic(int indeks)
{
    return (indeks - 1) / 2;
}

int Kopiec::l_dziecko(int indeks)
{
    return 2 * indeks + 1;
}

int Kopiec::p_dziecko(int indeks)
{
    return 2 * indeks + 2;
}




int main()
{
    Kopiec* heap = new Kopiec;

    std::random_device rd;
    std::default_random_engine generator(rd());
    std::uniform_int_distribution<long long> zakres_losowania(0, 10000);

    for (int i = 0; i < 100; i++)
        heap->Dodaj(zakres_losowania(generator));

    for (int i = 0; i < heap->rozmiar; i++)
        cout << heap->dane[i] << endl;

    heap->usun();
    cout << endl;
    for (int i = 0; i < heap->rozmiar-1; i++)
        cout << heap->dane[i] << endl;
}







//int Kopiec::znajdz_najwiekszy()
//{
//  if (rozmiar <= 0)
//      return INT_MAX;
//  if (rozmiar == 1)
//  {
//      rozmiar--;
//      return dane[0];
//  }
//
//  int root = dane[0];
//  dane[0] = dane[rozmiar - 1];
//  rozmiar--;
//  Kopcowanie_dol(0);
//
//  return root;
//}