public class Heap {
    private int[] heap;
    private int[] sortedList;
/**
 *  inicializa a lista de dados a serem ordenados
 * @param data lista de dados
 */
    public void setData(int[] data) {
        heap = new int[data.length];
        sortedList = new int[data.length];
        for (int i = 0; i < data.length; i++) {
            heap[i] = data[i];
        }
    }

    /**
   * ordena os elementos de uma lista
   * 
   * @param não
   *            recebe parâmetros
   * @return retorna a lista ordenada
   */
    public int[] sort() {
        construct(); // implementa o Heap
        extract(); // Extrai o maior valor do Heap
        return sortedList;
    }

    /**
   * constroi o Heap
   * 
   * @param não possui parâmetros
   * @return não possui valor de retorno
   */
    private void construct() {
        int current, maxChildIndex;
        boolean done;
        for (int i = (heap.length - 2) / 2; i >= 0; i--) {
            current = i;
            done = false;
            while (!done) {// constroi o heap
                // com o nó no índice i
                if (2 * current + 1 > heap.length - 1) {
                    // o nó atual não tem filho, então pára
                    done = true;
                } else {
                    // o nó atual tem pelo menos um nó filho
                    // busca o índice do maior filho
                    maxChildIndex = maxChild(current, heap.length - 1);
                    if (heap[current] < heap[maxChildIndex]) {
                        // o nó filho é maior, então troca e continua
                        swap(current, maxChildIndex);
                        current = maxChildIndex;
                    } else { // se todos os nós tiverem a condição 
                        // de valor satisfeita então para
                        done = true;
                    }
                }
            }
            assert isValidHeap(heap, i, heap.length - 1) : "Error: Construction phase is not working "
                    + "correctly";
        }
        testPrint(heap.length); // TEMP
    }

    /**
   * Extrai os valores do Heap
   * 
   * @param não possui parâmetros
   * @return não possui valor de retorno
   */
    private void extract() {
        int current, maxChildIndex;
        boolean done;
        for (int size = heap.length - 1; size >= 0; size--) {
            // remove o nó raiz
            sortedList[size] = heap[0];
            // move o último nó para o nó raiz
            heap[0] = heap[size];
            // reconstroi o heap com menos um elemento
            current = 0;
            done = false;
            while (!done) {
                if (2 * current + 1 > size) {
                    // o nó atual não tem nó filho, então pára.
                    done = true;
                } else {
                    // o nó atual tem pelo menos um nó filho
                    // busca o índice do maior filho
                    maxChildIndex = maxChild(current, size);
                    if (heap[current] < heap[maxChildIndex]) {
                        // se o filho for maior então troca e continua
                        swap(current, maxChildIndex);
                        current = maxChildIndex;
                    } else { // se todos os nós tiverem a condição 
                        // de valor satisfeita então para
                        done = true;
                    }
                }
            }
            testPrint(size); // TEMP
        }
    }
    /**
   * calcula o índice do maior nó filho
   * @param location índice do nó pai
   * @param end maior índice da lista
   * @return índice do maior nó filho
   */
    private int maxChild(int location, int end) {
        int result, leftChildIndex, rightChildIndex;
        rightChildIndex = 2 * location + 2;
        leftChildIndex = 2 * location + 1;

        assert leftChildIndex <= end : "Error: node at position " + location
                + "has no children.";
        if (rightChildIndex <= end
                && heap[leftChildIndex] < heap[rightChildIndex]) {
            result = rightChildIndex;
        } else {
            result = leftChildIndex;
        }
        return result;
    }
/**
 * Verificar se o heap obtido é válido
 * @param heap conjunto de valores do heap
 * @param start índice do primeiro nó 
 * @param end índice do último nó.
 * @return
 */
    private boolean isValidHeap(int[] heap, int start, int end) {
        for (int i = start; i < end / 2; i++) {
            if (heap[i] < Math.max(heap[2 * i + 1], heap[2 * i + 2])) {
                return false;
            }
        }
        return true;
    }
/**
 * Troca a posição de dois elementos
 * @param loc1 índice do primeiro elemento
 * @param loc2 índice do segundo elemento
 */
    private void swap(int loc1, int loc2) {
        int temp;
        temp = heap[loc1];
        heap[loc1] = heap[loc2];
        heap[loc2] = temp;
    }
/**
 * Imprime todos os valores
 * @param limit maior índice
 */
    private void testPrint(int limit) {
        for (int i = 0; i < limit; i++) {
            System.out.print(" " + heap[i]);
        }
        System.out.println(" ");
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] number = { 90, 44, 84, 12, 77, 23, 38, 5, 17 };
        int[] sortedList;
        Heap heap = new Heap();
        heap.setData(number); // assign the original list
        sortedList = heap.sort();// sort the list
        for (int i = 0; i < sortedList.length; i++) { // print out
            System.out.print(" " + sortedList[i]); // the sorted
        }

    }
}