HeapSort.java

/*
 * @author Marcelo Wischniowski <marcelowisc at gmail.com>
 */
public class HeapSort {

  /**
   * @param vetor Vetor que será ordenado Aplica a ordenação HeapSorte no vetor
   */
  public int[] sort(int[] vetor) {

    for (int i = vetor.length / 2 - 1; i >= 0; i--) {
      heapify(vetor, vetor.length, i);
    }

    for (int i = vetor.length - 1; i >= 0; i--) {

      int temp = vetor[0];
      vetor[0] = vetor[i];
      vetor[i] = temp;

      heapify(vetor, i, 0);
    }
    return vetor;
  }

  void heapify(int arr[], int arrayLength, int rootElementIndex) {

    int leftIndex = 2 * rootElementIndex + 1;
    int rightIndex = 2 * rootElementIndex + 2;

    int largest = rootElementIndex;

    if (leftIndex < arrayLength && arr[leftIndex] > arr[largest]) largest = leftIndex;

    if (rightIndex < arrayLength && arr[rightIndex] > arr[largest]) largest = rightIndex;

    if (largest != rootElementIndex) {

      int swap = arr[rootElementIndex];
      arr[rootElementIndex] = arr[largest];
      arr[largest] = swap;

      heapify(arr, arrayLength, largest);
    }
  }
}