Heap Sort
by Isai Damier, Android Engineer @ Google

/***************************************************************************
 * Author: Isai Damier
 * Title: Heapsort
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a disordered list of integers (or any other items),
 *   rearrange the integers in natural order.
 *
 * Sample Input: {8,5,3,1,9,6,0,7,4,2,5}
 * Sample Output: {0,1,2,3,4,5,5,6,7,8,9}
 *
 * Time Complexity of Solution:
 *   Best O(n*log(n)); Average O(n*log(n)); Worst O(n*log(n)).
 *
 * Approach:
 *   Heap sort happens in two phases. In the first phase, the array
 *   is transformed into a heap. A heap is a binary tree where
 *       1) each node is greater than each of its children
 *       2) the tree is perfectly balanced
 *       3) all leaves are in the leftmost position available.
 *    In phase two the heap is continuously reduced to a sorted array:
 *       1) while the heap is not empty
 *          - remove the top of the head into an array
 *          - fix the heap.
 *    Heap sort was invented by John Williams not by B. R. Heap.
 *
 * MoveDown:
 *   The movedown method checks and verifies that the structure is a heap.
 *
 * Technical Details:
 *   A heap is based on an array just as a hashmap is based on an
 *   array. For a heap, the children of an element n are at index
 *   2*n+1 for the left child and 2*n+2 for the right child.
 *
 *   The movedown function checks that an element is greater than its
 *   children. If not the values of element and child are swapped. The
 *   function continues to check and swap until the element is at a position
 *   where it is greater than its children.
 ***************************************************************************/ 
 public void heapsort(int[] input) {
  // convert input to heap
  int leastParent = (input.length - 1) / 2;
  for (int i = leastParent; i >= 0; i--) {
    moveDown(input, i, input.length - 1);
  }
  // flatten heap into sorted array
  for (int i = input.length - 1; i > 0; i--) {
    if (input[0] > input[i]) {
      swap(input, 0, i);
      moveDown(input, 0, i - 1);
    }
  }
}

private void moveDown(int[] input, int first, int last) {
  int largest = 2 * first + 1;
  while (largest <= last) {
    // right child exists and is larger than left child
    if (largest < last && input[largest] < input[largest + 1]) {
      largest++;
    }
    // right child is larger than parent
    if (input[largest] > input[first]) {
      swap(input, largest, first);
      // move down to largest child
      first = largest;
      largest = 2 * first + 1;
    } else {
      return;// force exit
    }
  }
}

private void swap(int[] input, int a, int b) {
  int tmp = input[a];
  input[a] = input[b];
  input[b] = tmp;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {
  
  @Test
  public void testHeapsort() {
    System.out.println(""heapsort"");
    int[] input = {8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5};
    Sorting instance = new Sorting();
    instance.heapsort(input);
    for (int i = 1; i < input.length; i++) {
      if (input[i - 1] > input[i]) {
        fail(""heapsort method fails."");
      }
    }
  }
}