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

template <class T>
class DynamicArray {
public:
	int size;
	int elements;
	T* array;

	DynamicArray() {
		size = 1;
		elements = 0;
		array = new T[size];
	}

	~DynamicArray() {

		delete[]array;

	}

	void expandArray() {
		size *= 2;
		T* tmpArray = new T[size];

		for (int i = 0; i < elements; i++)
		{
			tmpArray[i] = array[i];
		}

		delete[] array;
		array = tmpArray;

	}

	void addElement(T data) {
		if (elements < size) {
			array[elements] = data;
			elements++;
		}
		else {
			expandArray();
			array[elements] = data;
			elements++;

		}
	}

	T getElement(int index) {
		if (index < size)
			return array[index];
	}

	void deleteElement(int index) {
		if (index < size) {

			for (int i = index; i < size; i++)
			{
				array[i] = array[i + 1];
			}
			array[size] = NULL;
			elements--;

		}
	}

	string toString(int numbersOfString) {
		string str;
		if (numbersOfString < elements) {
			for (int i = 0; i < numbersOfString; i++)
			{
				str += to_string(array[i]);
			}

		}
		return str;
	}

	void changeElement(int index, T data) {
		if (index < elements) {
			array[index] = data;
		}
	}

	void clear() {
		for (int i = size - 1; i >= 0; i--)
		{
			array[i] = NULL;
		}
		elements = 0;
	}
};

template <class T>
class Heap {
public:
	int size;
	DynamicArray<T>* array;
	Heap() {
size = 0;
	 array = new DynamicArray<T>();
	}

	void add(T data) {
		array->addElement(data);
		int i = size++;
		int j = (i - 1) / 2;
		while (i > 0 && array->getElement(i) > array->getElement(j)) {
			T tmp = array->getElement(j);
			array->changeElement(j, array->getElement(i));
			array->changeElement(i,tmp);
			i = j;
			j = (i - 1) / 2;
		}
	}
	void swap(int i,int j) {
		T tmp = array->getElement(j);
		array->changeElement(j, array->getElement(i));
		array->changeElement(i, tmp);
	}


	T deleteTop() {
		if (size > 0) {
			if (size == 1) {
				T element = array->getElement(0);
				size = 0;
				array->clear();
				return element;
			}
			T element = array->getElement(0);
			array->changeElement(0, array->getElement(size - 1));
			array->deleteElement(size - 1);
			size--;

			int i = 0;
			int j = i * 2 + 1;
			int k = i * 2 + 2;
			while (array->getElement(i) < array->getElement(j) || array->getElement(i) < array->getElement(k)) {

					if (array->getElement(j) > array->getElement(k)) {
						swap(i, j);
						i = j;
					}
					else {
						swap(i, k);
						i = k;
					}
					j = i * 2 + 1;
					k = i * 2 + 2;
					if (j > size || k > size) {
						break;
					}
					if (array->getElement(i) > array->getElement(j) || array->getElement(i) > array->getElement(k)) {
						break;
					}


			}


			return element;

		}
	}

	void printHeap() {
		for (int i = 0; i < size; i++) {
			cout<< i << " : " << array->getElement(i)  << " ojciec " << (i-1)/2 <<endl;
		}
	}
	void clear() {
		size = 0;
		array->clear();
	}

};

int main() {

	Heap<int>* kopiec = new Heap<int>();

	kopiec->add(25);
	kopiec->add(20);
	kopiec->add(15);
	kopiec->add(6);
	kopiec->add(17);
	kopiec->add(7);
	kopiec->add(13);
	kopiec->add(5);
	kopiec->add(1);
	kopiec->add(22);
	int a = kopiec->deleteTop();
	kopiec->printHeap();
	a = kopiec->deleteTop();
	a = kopiec->deleteTop();
	a = kopiec->deleteTop();
	a = kopiec->deleteTop();
	a = kopiec->deleteTop();
	a = kopiec->deleteTop();

	a = kopiec->deleteTop();
	a = kopiec->deleteTop();
	a = kopiec->deleteTop();
	kopiec->printHeap();

	return 0;
	/*
	const int MAX_ORDER = 2;
	int dane;
	int a;
	for (int o = 1; o <= MAX_ORDER; o++) {
		const int n = pow(10, o);
		clock_t t1 = clock();
		for (int i = 0; i < n; i++) {
			dane = rand();
			kopiec->add(dane);
		}
		clock_t t2 = clock();
		double time = (t2 - t1) / (double)CLOCKS_PER_SEC;
		cout << "czas dodania: ";
		cout << time << endl;
		t1 = clock();
		for (int i = 0; i < n; i++) {
			a = kopiec->deleteTop();
		}
		t2 = clock();
		time = (t2 - t1) / (double)CLOCKS_PER_SEC;
		cout << "czas usuniecia: ";
		cout << time << endl;


	}
	return 0;
	*/
}