Heap Sort

Tem um desempenho em tempo de execução muito bom em conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Alguns algoritmos de ordenação rápidos têm desempenhos espectacularmente ruins no pior cenário, quer em tempo de execução, quer no uso da memória.

O heapsort trabalha no lugar e o tempo de execução em pior cenário para ordenar n elementos é de O (n lg n). Lê-se logaritmo (ou log) de "n" na base 2. Para valores de n, razoavelmente grandes, o termo log n é quase constante, de modo que o tempo de ordenação é quase linear com o número de itens a ordenar.

O heapsort não é um algoritmo de ordenação estável. Porém, é possível adaptar a estrutura a ser ordenada de forma a tornar a ordenação estável. Cada elemento da estrutura adaptada deve ficar no formato de um par (elemento original, índice original). Assim, caso dois elementos sejam iguais, o desempate ocorrerá pelo índice na estrutura original.

Como tudo funciona

Mãos a obra:


    import java.util.ArrayList;
    import java.util.Random;
    import java.util.Scanner;
    
    public class heapSort {
    
        public static void main(String[] args) {
            Scanner leia = new Scanner(System.in);
            ArrayList lista = new ArrayList<>();
            int cont = 1;
    
            for (int i = 0; i < 1000; i++) {
                Random rand = new Random();
                int n = rand.nextInt(1000);
                lista.add(n);
            }
    
            heapSort(lista);
    
            for (Integer integer : lista) {
                System.out.print(integer + ", ");
                if (cont % 20 == 0) {
                    System.out.println();
                }
                cont++;
            }
        }
    
        /* ---------------------- Algoritimo De Ordenação ---------------------- */
        public static void heapSort(ArrayList lista) {
            int T = lista.size();
            for (int i = T / 2 - 1; i >= 0; i--) {
                montar(lista, T, i);
            }
            for (int i = T - 1; i > 0; i--) {
                int aux = lista.get(0);
                lista.set(0, lista.get(i));
                lista.set(i, aux);
    
                montar(lista, i, 0);
            }
        }
    
        public static void montar(ArrayList lista, int T, int i) {
            int maior = i;
            int l = 2 * i + 1;
            int r = 2 * i + 2;
    
            if (l < T && lista.get(l) > lista.get(maior)) {
                maior = l;
            }
    
            if (r < T && lista.get(r) > lista.get(maior)) {
                maior = r;
            }
    
            if (maior != i) {
                int aux = lista.get(i);
                lista.set(i, lista.get(maior));
                lista.set(maior, aux);
    
                montar(lista, T, maior);
            }
        }
    }

Tempo de execução(em segundos) VS Qtd de nº no Array:

Heap Sort	1.000	10.000	500.000	1.000.000
Bom	0.0127284	0.0427259	0.5023161	0.7884551
Médio	0.0023638	0.0131837	1.047212	1.5117239
Ruim	0.002532	0.0106745	0.5357476	0.6776987

*A tabela representa a quantidade de numros utilizadas e o tempo de execução o processo de ordenação