heap_sort.java

public int parent(int i) {
  return (i-1)/2;
}

public int left(int i) {
  return i*2+1;
}

public int right(int i) {
  return left(i)+1;
}

public void maxHeapify(int[] arr, int i, int length) {
  if (length == 0) return;
  int hv = arr[i];
  int l = left(i);
  int r = right(i);
  int max = hv;
  int ti = i;
  if (l < length && arr[l] > arr[ti]) ti = l;
  if (r < length && arr[r] > arr[ti]) ti = r;
  if (ti != i) {
    swap(arr, ti, i);
    maxHeapify(arr, ti);
  }
}

public void buildMaxHeap(int[] arr) {
  if (arr.length == 0) return;
  for (int i = parent(arr.length-1); i>=0; i--) {
    maxHeapify(arr, i, arr.length);
  }
}

public void heapSort(int[] arr) {
  if (arr.length == 0) return;
  buildMaxHeap(arr);
  for (int i = arr.length-1; i>=0; i--) {
    swap(i, 0);
    maxHeapify(arr, 0, i);
  }
}