HeapSort

package com.company;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // write your code here
        int i = 0;
        Scanner sc = new Scanner(System.in);
        System.out.println("Please enter the input and when finish write DONE");
        ArrayList<String> list = new ArrayList<String>();
        list.add(sc.nextLine());
        while (!list.get(i).equalsIgnoreCase("DONE")) {
            list.add(sc.nextLine());
            i++;
        }
        list.remove(i);
        int[] arry =new int[i];
        arry = stringTOint(list, i);
        HeapSort(arry, i);
        printHeap(arry);
    }

    public static int[] stringTOint(ArrayList<String> list, int i) {
        int[] arr = new int[i+1];
        for (int index = 0; index <i; index++) {
            arr[index+1] = Integer.valueOf(list.get(index));
        }
        return arr;
    }

    public static void Heapify(int[] arr, int i, int n) {
        int p = i;
        int left = 2*p;
        int right = 2*p + 1;
        int largest = i;
        if (left <= n && arr[left] > arr[i]) largest = left;
        if (right <= n && arr[right] > arr[largest]) largest = right;
        if (i != largest) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            Heapify(arr, largest, n);
        }
    }

    public static void buildHeap(int[] arr, int n) {
        for (int p = (n / 2); p > 0; p--) Heapify(arr, p, n);
    }

    public static void HeapSort(int[] arr, int n) {
        buildHeap(arr, n);
        for (int s = n; s > 1; s--) {
            int temp = arr[1];
            arr[1] = arr[s];
            arr[s] = temp;
            n--;
        }
    }

    public static void printHeap(int[] arr) {
        System.out.println("The sorted List");
        for (int p = 1; p < arr.length; p++) {
            System.out.print(arr[p] + "\t");
        }
    }
}