class Kopiec
{
public:
	int liczbaElementow;
private:
	int *w;
	string gornyRog, dolnyRog, pion;
public:
	Kopiec()
	{
		gornyRog = dolnyRog = pion = "  ";
		gornyRog[0] = 218; gornyRog[1] = 196;
		dolnyRog[0] = 192; dolnyRog[1] = 196;
		pion[0] = 179;
		liczbaElementow = 0;
		w = new int[liczbaElementow + 1];
	}
	~Kopiec()
	{
		liczbaElementow = 0;
		delete[] w;

	}
	void zapelnijLosowo(int ile)
	{
		liczbaElementow = ile;
		w = new int[liczbaElementow + 1];
		for (int i = 1; i <= liczbaElementow; i++)
			w[i] = ((rand() % 2000) - 1000);
		budujKopiec();
	}

	void zbudujZPliku(string nazwa)
	{
		string s;
		int i = 0;
		int *t;
		nazwa = nazwa + ".txt";
		ifstream plik(nazwa);

		if (!plik)
		{
			cout << "Nie mozna otworzyc pliku" << endl;;

		}
		else
		{
			getline(plik, s);
			int n = atoi(s.c_str());
			liczbaElementow = n;
			t = new int[liczbaElementow];
			while (!plik.eof())
			{
				if (i <= liczbaElementow)
				{
					getline(plik, s);
					t[i] = atoi(s.c_str());
					i++;
				}
				else break;
			}
			plik.close();
			for (i; i <= liczbaElementow; i++)
			{
				t[i] = 0;
			}
			w = t;
			budujKopiec();
		}
	}
	void budujKopiec()
	{
		for (int i = 2; i <= liczbaElementow; i++)
		{
			int pozycjaElementu, pozycjaPrzodka, element;
			pozycjaElementu = i;
			pozycjaPrzodka = (pozycjaElementu) / 2;
			element = w[i];
			while ((pozycjaPrzodka > 0) && (w[pozycjaPrzodka] < element))
			{
				w[pozycjaElementu] = w[pozycjaPrzodka];
				pozycjaElementu = pozycjaPrzodka;
				pozycjaPrzodka = (pozycjaElementu) / 2;
			}
			w[pozycjaElementu] = element;
		}
	}
	void wyswietl(string tekst1, string tekst2, int nrWezla)
	{
		if (liczbaElementow == 0)
			cout << "Kopiec jest pusty" << endl;
		string tekst;

		if (nrWezla <= liczbaElementow)
		{
			tekst = tekst1;
			if (tekst2 == gornyRog)
				tekst[tekst.length() - 2] = ' ';

			wyswietl(tekst + pion, gornyRog, 2 * nrWezla + 1);

			tekst = tekst.substr(0, tekst1.length() - 2);

			cout << tekst << tekst2 << w[nrWezla] << endl;

			tekst = tekst1;
			if (tekst2 == dolnyRog)
				tekst[tekst.length() - 2] = ' ';
			wyswietl(tekst + pion, dolnyRog, 2 * nrWezla);
		}
	}
	bool szukaj(int liczbaDoZnalezienia)
	{
		bool czyJest = false;
		for (int i = 1; i <= liczbaElementow; i++)
		{
			if (liczbaDoZnalezienia == w[i])
			{
				czyJest = true;
				break;
			}
		}
		return czyJest;

	}
	void dodaj(int liczbaDoDodania)
	{
		licznik = 0;
		czasStart();
		liczbaElementow++;
		w[liczbaElementow] = liczbaDoDodania;
		int pozycjaNowegoElementu = liczbaElementow;
		while ((w[pozycjaNowegoElementu] > w[pozycjaNowegoElementu / 2]) && (pozycjaNowegoElementu > 1))
		{
			int temp = w[pozycjaNowegoElementu / 2];
			w[pozycjaNowegoElementu / 2] = w[pozycjaNowegoElementu];
			w[pozycjaNowegoElementu] = temp;
			pozycjaNowegoElementu = (pozycjaNowegoElementu / 2);
		}
		pobierzCzas();
	}
	void relokuj()
	{
		int *t = new int[liczbaElementow + 1];
		for (int i = 1; i <= liczbaElementow; i++)
		{
			t[i] = w[i];
		}
		w = new int[liczbaElementow + 1];
		for (int i = 1; i <= liczbaElementow; i++)
		{
			w[i] = t[i];
		}
		delete[]t;
	}
	void usun(int liczbaDoUsuniecia)
	{

		if (liczbaElementow == 0)
			cout << "Kopiec jest pusty, nie mozna nic usunac" << endl;
		else
		{
			if (!szukaj(liczbaDoUsuniecia))
				cout << "W kopcu nie ma takiej liczby, nie mozna usunac!" << endl;
			else
			{
				licznik = 0;
				czasStart();
				int i;
				for (i = 1; i <= liczbaElementow; i++)
				{
					if (w[i] == liczbaDoUsuniecia) break;
				}
				if (i == liczbaElementow)
				{
					w[i] = NULL;
					liczbaElementow--;
					pobierzCzas();
				}
				if (i < liczbaElementow)
				{
					w[i] = w[liczbaElementow];
					w[liczbaElementow] = NULL;
					liczbaElementow--;
					if (2 * i > liczbaElementow)
					{
						while (i > 1)
						{
							if (w[i] > w[i / 2])
							{
								int temp = w[i / 2];
								w[i / 2] = w[i];
								w[i] = temp;
							}
							i = i / 2;
						}
					}
					else
					{
						while (i <= liczbaElementow / 2)
						{
							if ((w[i] < (w[2 * i])) || (w[i] < (w[2 * i + 1])))
							{
								if (w[2 * i] > w[2 * i + 1])
								{
									int temp = w[i];
									w[i] = w[2 * i];
									w[2 * i] = temp;
									i = 2 * i;
								}
								else
								{
									int temp = w[i];
									w[i] = w[2 * i + 1];
									w[2 * i + 1] = temp;
									i = 2 * i + 1;
								}
							}
							else break;
						}

					}
				}
				pobierzCzas();
				relokuj();
			}
		}
	}
};