Kopiec

//ALGO2 IS1 211A LAB04
//Jakub Ogryzek
//oj44443@zut.edu.pl
#include "pch.h"
#include <iostream>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <memory>
#include <string>
#include <random>

using namespace std;

template <typename T>
class Heap {
public:
    T *data = new T[capacity];
    int capacity;
    int size;
    Heap()
    {
        size = 0;
        capacity = 1;
        data = new T[capacity];
    }
    ~Heap()
    {
        delete[] data;
        data = nullptr;
        size = 0;
        capacity = 0;
    }

    int Push(int size)
    {
        if (size == 0)
            return 0;
        int parent_index = parent(size);
        if (parent_index == -1000)
            return 0;
        if (data[size] <= data[parent_index])
            return 0;
        else {
            swap(data[size], data[parent_index]);
            Push(parent_index);
        }
    }

    void AddNewElement(const T&input)
    {
        size = size + 1;
        if (size <= capacity) {
            data[size - 1] = input;
        }
        if (size > capacity)
        {
            capacity = capacity * 2;
            T *temp = new T[capacity];
            for (int i = 0; i < size - 1; i++)
            {
                temp[i] = move(data[i]);
            }
            temp[size - 1] = input;
            delete[] data;
            data = temp;
        }
        Push(size - 1);
    }

    void DeleteRoot(int index)
    {
        data[0] = data[index];
        //data[index] = NULL;
        DeleteRootRek(0);
        size = size - 1;
    }

    int DeleteRootRek(int index)
    {
        int left = left_son(index);
        int right = right_son(index);
        if (data[index] > data[left] && data[index] > data[right])
            //wezel ma wieksza wartosc od obydwu dzieci
            return 0;
        if (data[index] > data[left] && data[index] < data[right]) {
            //idziemy w prawo
            swap(data[index], data[right]);
            DeleteRootRek(right);
        }
        if (data[index] < data[left] && data[index] > data[right]) {
            //idziemy w lewo
            swap(data[index], data[left]);
            DeleteRootRek(left);
        }
        if (data[index] < data[left] && data[index] < data[right]) {
            //obydwa dzieci maja wieksza wartosc i idziemy tam gdzie wartosc jest wieksza
            if (data[left] > data[right]) {
                swap(data[index], data[left]);
                DeleteRootRek(left);
            }
            if (data[left] < data[right]) {
                swap(data[index], data[right]);
                DeleteRootRek(right);
            }
        }
    }

    void swap(T&x, T&y)
    {
        T temp;
        temp = x;
        x = y;
        y = temp;
    }

    int parent(int index)
    {
        if (index > 0)
            return (index - 1) / 2;
        else {
            cout << "Rodzic tego elementu nie istnieje" << endl;
            return -1000;
        }
    }
    int left_son(int index)
    {
        if (2 * index + 1 < size)
            return 2 * index + 1;
        else {
            cout << "Ten element nie ma lewego syna" << endl;
            return -1000;
        }
    }
    int right_son(int index)
    {
        if (2 * index + 2 < size)
            return 2 * index + 2;
        else {
            cout << "Ten element nie ma prawego syna" << endl;
            return -1000;
        }
    }

    void ToString()
    {
        cout << "Kopiec:" << endl;
        cout << "Liczba elementow: " << size << endl;
        int dzielenie = 1;
        for (int i = 0; i < size; i++)
        {
            cout << data[i] << ", ";
        }
    }

    void ClearHeap()
    {
        cout << "Kopiec zostal wyczyszczony" << endl;
        for (int i = 0; i < size; i++)
        {
            data[i].~T();
        }
        size = 0;
        capacity = 1;
    }
};

struct Struktura
{
    int pole1;
    Struktura()
    {
        const int MAX_ORDER = 8;
        const int n = pow(10, MAX_ORDER);
        std::random_device rd;
        std::default_random_engine generator(rd());
        std::uniform_int_distribution<long long> zakres(1, n);
        pole1 = zakres(generator);
    }
    Struktura(int a)
    {
        pole1 = a;
    }
    bool operator ==(const Struktura&n) const
    {
        return pole1 == n.pole1;
    }
    bool operator >(const Struktura&n) const
    {
        return pole1 > n.pole1;
    }
    bool operator <(const Struktura&n) const
    {
        return pole1 < n.pole1;
    }
    bool operator <=(const Struktura&n) const
    {
        return pole1 <= n.pole1;
    }
    bool operator >=(const Struktura&n) const
    {
        return pole1 >= n.pole1;
    }
};

ostream& operator <<(ostream&stream, const Struktura&m)
{
    return (stream << m.pole1); //<< m.pole2);
}

int main()
{
    const int MAX_ORDER = 7;
    Heap<Struktura>*binary_heap = new Heap<Struktura>();
    //for (int o = 1; o <= MAX_ORDER; o++)
    //{
        const int n = pow(10, 1);
        clock_t t1 = clock();
        for (int i = 0; i < n; i++)
        {
            binary_heap->AddNewElement(Struktura{});
        }
        clock_t t2 = clock();
        cout << "Czas wykonania operacji dodawania " << n << " elementow to: " << (double)(t2 - t1) / CLOCKS_PER_SEC << " sekundy" << endl;
    //}
    system("pause");
    //binary_heap->DeleteRoot(binary_heap->size - 1);
    binary_heap->ClearHeap();
    delete binary_heap;





    /*Heap<int>* heap = new Heap<int>();
    heap->AddNewElement(1); //0
    heap->AddNewElement(2); //1
    heap->AddNewElement(3); //2
    heap->AddNewElement(4); //3
    heap->AddNewElement(5); //4
    heap->AddNewElement(6); //5
    heap->AddNewElement(7); //6
    heap->AddNewElement(8);
    heap->AddNewElement(9);
    heap->AddNewElement(10);
    heap->AddNewElement(11);
    heap->AddNewElement(12);
    heap->AddNewElement(13);
    heap->AddNewElement(14);
    heap->AddNewElement(15);
    //heap->DeleteRoot(heap->size - 1);
    heap->ToString();
    //heap->ClearHeap();
    delete heap;*/
}