#include <iostream>
#include "vector"
#include "xutility"


using namespace std;
//Swap elements in array
void Swap(vector<int>& vHeap, vector<int>::size_type i, vector<int>::size_type j)
{
	if (i == j)
	{
		return;
	}

	int temp;
	temp = vHeap[i];
	vHeap[i] = vHeap[j];
	vHeap[j] = temp;
}
// search and compare the elements in array and subsequently swap them
//to their rightful spot
void Sift(vector<int>& vHeap, const vector<int>::size_type heapSize, const vector<int>::size_type siftNode)
{
	vector<int>::size_type i, j;
	j = siftNode;
	do
	{
		i = j;
		if (((2*i +1)< heapSize) && vHeap[j] < vHeap[2*i +1])
		{
			j = 2 * i + 1;
		}
		if (((2 * i + 2) < heapSize) && vHeap[j] < vHeap[2 * i + 2])
		{
			j = 2 * i + 2;
		}
		Swap(vHeap, i, j);
	} while (i!= j);
}
void MakeInitialHeap(vector<int>& vHeap)
{
	for (int i = vHeap.size() -1; i >= 0; --i)
	{
		Sift(vHeap, vHeap.size(), i);
	}
}
// Actual sorting of the array
vector<int> HeapSort(vector<int>& vHeap)
{
	vector<int> NewHeap;
	MakeInitialHeap(vHeap);
	for (vector<int>::size_type i = vHeap.size() - 1; i > 0; --i)
	{
		Swap(vHeap, i, 0);
		Sift(vHeap, i, 0);
		NewHeap.push_back(vHeap[i]);
	}
	return NewHeap;
}

int IntSearch(vector<int>& Arr, int e)// Interpolation Search
{
	int _end = Arr.size()-1;
	int _start = 0;
	int _pos = 0;

	while (_start <= _end && e >= _start && e <= Arr[_end])
	{
		_pos = _start + (((_end - _start) / (Arr[_end] - Arr[_start]))* (e - Arr[_start]));
		if (Arr[_pos] == e)
		{
			return _pos;
		}
		if (e > Arr[_pos])
		{
			_start = _pos + 1;
		}
		else
		{
			_end = _pos - 1;
		}
	}
	return -1;


}

int main()
{
	vector<int> PrimeList = { 2,199, 3, 43, 47, 5, 7, 109, 113, 127, 11, 17,  31, 37,
		41, 53, 59, 61, 67, 179, 181, 71, 73, 79, 83,
		89, 97, 101, 103,19, 23, 29, 107, 131, 137,
		139,  167, 173, 191, 149, 151, 157, 163, 193, 197,13 };//array of unsorted prime numbers up to 200.
	int x;
	char ch;
	HeapSort(PrimeList);
	for (vector<int>::size_type i = 0; i < PrimeList.size(); i++)
	{
		cout << PrimeList[i] << endl;
	}
up:// Label, in case the user wants to search again.
	cout << "\nEnter the Prime Number you want to search for: ";
	cin >> x;
	int _result = IntSearch(PrimeList,x);
	if (_result == -1)
		cout << "Element not Found!" << endl;
	else if (_result != -1)
	{
		cout << "The number " << x << "was found at the " << _result << " place in the list." << endl;
	}
	cout << "Would you like to do another search? (y/n)" << endl;
	cin >> ch;
	if (ch == 'Y'||ch == 'y')
	{
		goto up;// go back to the label.
	}

	return 0;
}