struct element
{
	int data;
	short int index;
	element(int data,short int index)
	{
		this->data = data;
		this->index = index;
	}
	element()
	{
		data = 0;
		index = 0;
	}
};
class MaxHeap
{
	int* myarray;
	int size;
	int counter;

public:
	int parent(int i) { return (i/2); }
	int left(int i) { return (2*i); }
	int right(int i) { return (2*i+1); }
	void create(int size)
	{
		 this->size = (size+1);
		 counter = 1;
		 myarray = new int[size+1];
		 myarray[0] = 1;

	}
	void Heapify(int index)
	{

		int max = index;
		int right = this->right(index);
		int left = this->left(index);
		if (right<counter && myarray[right]>myarray[max])
		{
			max = right;
		}
		if (left<counter && myarray[left]>myarray[max])
		{
			max = left;
		}
		if (max != index)
		{
			swap(myarray[index], myarray[max]);
			Heapify(max);
		}

	}
	bool isEmpty()
	{
		return (counter == 1);
	}
	void insert(int value)
	{

		if (counter == size)
		{
			cout << "array is full" << endl;
			return;
		}
		myarray[counter++] = value;
		int i = counter-1;
		while (i != 1 && myarray[this->parent(i)] < myarray[i])
		{
			swap(myarray[i], myarray[i / 2]);
			i = this->parent(i);
		}
    }
	void print() const
	{
		int j = 1;
		while (j < counter)
		{
			cout << myarray[j++] << " ";
		}
		cout << endl;
    }
	int getMax()
	{
		if (isEmpty())
		{
			cout << "Haep is empty" << endl;
			return 0;
		}
		else
		{
			int max = myarray[1];
			myarray[1] = myarray[counter-1];
			counter--;

			Heapify(1);
			return max;
		}
    }
	int get_size()
	{
		return counter;
	}
};