#include <iostream>
#include <time.h>
#include <exception>
#include <random>
#include <string>
template <typename T>
struct node {
	node() {};
	node(T value) : data(value) {}
	T data;
};

template <typename T>
struct kopiec {
	long int size = 0;
	long int capacity = 1;
	node<T>* table = new node<T>[capacity];
	kopiec() {

	}
	kopiec(T* tablica, int rozmiar) {
		size = rozmiar;
		for (int i = 0; i <= size; i++) {
			table[i] = *(tablica + i);
		}
		przekopcowanieRekWDol(0);
	}
	~kopiec() {
		delete[] table;
	}
	int leftChild(int indeks) {
		int left = 2 * indeks;
		if (left <= size && left >= 0) {
			return left;
		}
		else {
			return -1;
		}
	}
	int rightChild(int indeks) {
		int right = 2 * indeks + 1;
		if (right <= size && right >= 0) {
			return right;
		}
		else {
			return -1;
		}
	}
	int parent(int indeks) {
		if (indeks > 0) {
			int rodzic = (indeks - 1) / 2;
			if (rodzic <= size && rodzic >= 0) {
				return rodzic;
			}
			else {
				return -1;
			}
		}
		else {
			return -1;
		}
	}
	T getAndDeleteMax() {
		T chwilowy = table[0].data;

		size--;
		table[0] = table[size];

		//przesunięcie tablicy o 1 w lewo
		/*for (int i = 0; i < size; i++) {
			table[i].data = table[i + 1].data;
		}

		if (table[0].data < table[1].data) {
			T chwilowyII = table[0].data;
			table[0].data = table[1].data;
			table[1] = chwilowyII;
		}
		if (table[0].data < table[2].data) {
			T chwilowyII = table[0].data;
			table[0].data = table[2].data;
			table[2] = chwilowyII;
		}*/
		przekopcowanieRekWDol(0);

		return chwilowy;
	}
	void addNewNode(node<T> newData) {
		if (size < capacity) {
			table[size] = node<T>{ newData };
			size++;
		}
		else {
			capacity = capacity * 2;
			node<T>* biggerTable = new node<T>[capacity];
			for (int i = 0; i < size; i++) {
				biggerTable[i] = table[i];
			}
			delete[] table;
			table = biggerTable;
			table[size] = node<T>{ newData };
			size++;
		}
		if (size > 1) {
			przekopcowanieRekWGore(size - 1);
		}
	}
	void deleteAll() {
		delete[] table;
	}
	void showAll() {
		for (int i = 0; i < size; i++) {
			std::cout << table[i];
		}
	}
	void przekopcowanieRekWGore(int indeks) {
		auto rodzic = parent(indeks);
		if (rodzic >= 0) {
			T chwilowy = table[rodzic].data;
			if (indeks > 0 && chwilowy < table[indeks].data)
			{
				table[rodzic].data = table[indeks].data;
				table[indeks].data = chwilowy;
				przekopcowanieRekWGore(rodzic);
			}
		}
		else {
			//std::cout << "przekopcowaniewgore nie tak" << std::endl;
		}
	}
	void przekopcowanieRekWDol(int indeks) {
		int largest = indeks;
		int left = leftChild(indeks);
		int right = rightChild(indeks);

		if (left > 0 && table[left].data > table[largest].data) {
			largest = left;
		}
		else if (right > 0 && table[right].data > table[largest].data) {
			largest = right;
		}
		if (largest != indeks) {
			node<T> chwilowy;
			chwilowy.data = table[indeks].data;
			table[indeks].data = table[largest].data;
			table[largest] = chwilowy;
			//std::cout << indeks << std::endl;
			przekopcowanieRekWDol(largest);
		}
	}
};

template <typename T>
std::ostream& operator<<(std::ostream& out, const node<T>& val) {
	out << val.data << std::endl;
	return out;
}

int main() {
	std::random_device rd;
	std::mt19937 gen(rd());
	std::uniform_int_distribution<int> losowa(1, 10000);
	const int MAX_ORDER = 1; // maksymalny rzad wielkosci dodawanych danych

	double time1 = 0;
	double time2 = 0;


	for (int o = 1; o <= MAX_ORDER; o++)
	{
		int n = 0;
		kopiec <int> example; // stworzenie kopca
		clock_t t1 = clock();
		//dodawanie do kopca
		for (int i = pow(10, o); i > 0; i--)
		{
			int liczba = losowa(gen);
			example.addNewNode(i);

			n++;
		}
		clock_t t2 = clock();

		std::cout << std::endl;
		time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
		//pobieranie i usuwanie elemntu maksymalnego kopca
		clock_t t3 = clock();
		for (int i = 0; i < n; i++) {
			auto cos = example.getAndDeleteMax();
			example.showAll();
			std::cout << std::endl;
		}
		clock_t t4 = clock();
		time2 = (t4 - t3) / (double)CLOCKS_PER_SEC;

		std::cout << "Czas dodawania " << n << " elemenow: " << time1 << std::endl;
		std::cout << "Czas pobierania i kasowania maxow: " << time2 << std::endl;
	}
	std::cout << "koniec" << std::endl;
	getchar();
}