#include <iostream>

using namespace std;

int i=0;
string name[100];
int input[100];

void heapify(int arr[], string arrN[], int n, int i)
{
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    // if left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // if right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // if largest is not root
    if (largest != i)
    {
        swap(arr[i], arr[largest]);
        swap(arrN[i],arrN[largest]);

        // recursively heapify the affected sub-tree
        heapify(arr,arrN, n, largest);
    }
}

void heapSort(int arr[], string arrN[], int n)
{
    // build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, arrN, n, i);

    // one by one extract an element from heap
    for (int i=n-1; i>=0; i--)
    {
        // move current root to end
        swap(arr[0], arr[i]);
        swap(arrN[0],arrN[i]);

        // call max heapify on the reduced heap
        heapify(arr,arrN, i, 0);
    }
}

/* function to print array of size n */
void printArray(int arr[],string arrN[], int n)
{
    for (int i = 0; i < n; i++)
    {
    	cout << (i+1) << ". "<< arrN[i];
        cout << " - " << arr[i] << " Php" <<  endl;

    }
}




int mainUI()
{
	int choices;

	cout << "Welcome to Kenneth's Workshop" << endl << endl;
	cout << " [0] View all Employees" << endl;
	cout << " [1] Add Employees(With Salary)" << endl;
	cout << " [2] Exit Program" << endl;

	cin >> choices;
	switch(choices)
	{
		case 0:
			{

				cout << " VIEW ALL EMPLOYEES ALONG THEIR SALARIES" << endl << endl;

				string names[i];
				int salary[i];
				for(int j = 0; j <i ; j++)
				{
				if(j == i+1)
				{
					break;
				}
				names[j] = name[j];
				salary[j] = input[j];
				}
				int n = sizeof(salary)/sizeof(salary[0]);

    			heapSort(salary, names, n);
				printArray(salary,names, n);
				system("pause");
				system("cls");
				mainUI();
 			}
		case 1:
			{
				system("cls");
				while(true){
        			cout << "Enter all of your data here" << endl << endl;
        			cout << "Enter name of employee: ";
        			cin >> name[i];

        			if(name[i]=="~"){
            			break;
        				}

        			cout << "Enter salary: ";
        			cin >> input[i];
        			i++;
        			system("cls");
    			}
    			system("cls");
    			mainUI();
			}
		case 2:
			{
				return 0;
			}
	}
}

int main(){
	mainUI();

	return 0;

}