TOP 25 ALGORITMOS | Heap Sort

#Estrutura de dados

É uma técnica de classificação baseada em comparação baseada na Binary Heap Data Structure. Pode ser vista como uma otimização sobre a classificação por seleção, onde primeiro encontramos o elemento máximo (ou mínimo) e o trocamos com o último (ou primeiro). Repetimos o mesmo processo para os elementos restantes.

📁 | Resumo

🤖 | Código


function heapify(arr, n, i) {

  // Inicializa o maior como raiz
  let largest = i;
  
  // Index da esquerda = 2*i + 1
  let l = 2 * i + 1; 
  
  // Index da direita = 2*i + 2
  let r = 2 * i + 2; 

  // Se o filho da esquerda for maior que a raiz
  if (l < n && arr[l] > arr[largest]) {
      largest = l;
  }

  // Se o filho da direita for maior que o largest até agora
  if (r < n && arr[r] > arr[largest]) {
      largest = r;
  }

  // Se o maior não for raiz
  if (largest !== i) {
      let temp = arr[i]; // Swap
      arr[i] = arr[largest];
      arr[largest] = temp;

      // Heapificar recursivamente a subárvore afetada
      heapify(arr, n, largest);
  }
}

// Função principal para fazer heap sort
function heapSort(arr) {
  let n = arr.length;

  // Construir heap (rearrange array)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
      heapify(arr, n, i);
  }

  // Extrai um por um um elemento do heap
  for (let i = n - 1; i > 0; i--) {
  
      // Mover a raiz atual para o fim
      let temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;

      // Chama max heapify no heap reduzido
      heapify(arr, i, 0);
  }
}

// Uma função utilitária para imprimir um array de tamanho n
function printArray(arr) {
  for (let i = 0; i < arr.length; i++) {
      console.log(arr[i] + " ");
  }
  console.log();
}

🕰️ | Complexidade de Tempo

O tempo de execução do algoritmo cresce em função do tamanho da entrada n multiplicado pelo logaritmo de n. Esse tipo de complexidade geralmente aparece em algoritmos que combinam operações lineares com alguma forma de divisão e conquista. Logo, sua complexidade de tempo será descrita por O(n ∙ log(n)).

📦 | Complexidade de Espaço

A quantidade de memória que um algoritmo usa cresce de forma logarítmica em relação ao tamanho da entrada n. Isso significa que, mesmo que a entrada n aumente significativamente, o espaço adicional necessário cresce lentamente. Logo, sua complexidade de espaço será descrita por O(log(n)).

✔️ | Vantagens

✦ Rápido, econômico e simples;

❌ | Desvantagens

✦ Instabilidade e ineficiência;