void print(vector<int>& arr){
		for(auto ele : arr)
			cout<<ele<<" ";
		cout<<endl;
		}
	void maxHeapify(int i, vector<int>& arr, int n){
		vector<int> arr = this->arr;
		int left = 2*i + 1 , right = 2*i+2;
		int largest = i;
		if( left < n && arr[left] > arr[largest])
			largest = left;
		if(right < n && arr[right] > arr[largest])
			largest = right;
		if(largest != i){
			swap(arr[largest] , arr[i]);
			maxHeapify(largest, arr , n);
		}
	}

	void formMaxHeap(vector<int>& arr){
		int n = arr.size();
		int r = (n/2) -1;
		for(int i = r; i>=0; i--){
			maxHeapify(i, arr, n);
		}
	}
	int extract_max(vector<int>& arr){
		int val = arr.front();
		swap(arr.front(), arr.back());
		arr.pop_back();
		int size= arr.size();
		maxHeapify(0, arr, size);
		return val;
	}
	void heapSort(vector<int>& arr){
		int n = arr.size() ;
		formMaxHeap(arr);
		for(int r  = n-1 ; r > 0 ; r--){
			swap(arr[0], arr[r]);
			maxHeapify(0, arr, r );
		}

	}