HeapSort

import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    Test test = new Test();
    test.runTests();
  }
}

class Test{
  private HeapSort heapSort;
  private int[] array;
  
  public void runTests(){
    startTest();
    array = new int[]{16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
    System.out.println("Before: " + Arrays.toString(array));
    
    heapSort.maxHeapify(array, 1);
    System.out.println("After Max Heapify: " + Arrays.toString(array));
    
    startTest();
    array = new int[]{4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    System.out.println("Before: " + Arrays.toString(array));
    
    heapSort.buildMaxHeap(array);
    System.out.println("After Build Max Heap: " + Arrays.toString(array));
    
    startTest();
    array = new int[]{4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    System.out.println("Before: " + Arrays.toString(array));
    
    System.out.println("After HeapSort: " +
                       Arrays.toString(heapSort.sort(array)));
  }
  
  private void startTest(){
    heapSort = new HeapSort();
  }
}

class HeapSort{
  public int[] sort(int[] array){
    int[] result = new int[array.length];
    buildMaxHeap(array);
    for(int i = 0; i < array.length; i++){
      result[array.length - 1 - i] = array[0];
      array[0] = array[array.length - 1 - i];
      array[array.length - 1 - i] = Integer.MIN_VALUE;
      maxHeapify(array, 0);
    }
    return result;
  }
  
  public void buildMaxHeap(int[] array){
    for(int i = (int)Math.floor((array.length - 1)/2.0); i >= 0; i--){
      maxHeapify(array, i);
    }
  }
  
  public void maxHeapify(int[] array, int index){
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int largest = 0;
    int tmp = 0;
    
    if(left < array.length && array[left] > array[index]){
      largest = left;
    }else{
      largest = index;
    }
    if(right < array.length && array[right] > array[largest]){
      largest = right;
    }
    if(largest != index){ // exchange
      tmp = array[index];
      array[index] = array[largest];
      array[largest] = tmp;
      maxHeapify(array, largest);
    }
  }
}