¿Qué es Heap Sort?

Heap Sort es un algoritmo de ordenamiento basado en un árbol binario llamado "heap". Construye un max heap del arreglo y, a continuación, intercambia el elemento más grande (la raíz) con el último elemento del arreglo, reduciendo el tamaño del heap y repitiendo el proceso.

El Código

                
function heapSort(arr) {
  let n = arr.length;

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

  // Extraer elementos del heap uno por uno
  for (let i = n - 1; i > 0; i--) {
    // Mover la raíz actual al final
    [arr[0], arr[i]] = [arr[i], arr[0]];

    // Llamar a heapify en el heap reducido
    heapify(arr, i, 0);
  }

  return arr;
}

function heapify(arr, n, i) {
  let largest = i; // Inicializar el más grande como raíz
  let left = 2 * i + 1; // izquierda = 2*i + 1
  let right = 2 * i + 2; // derecha = 2*i + 2

  // Si el hijo izquierdo es más grande que la raíz
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  // Si el hijo derecho es más grande que el más grande hasta ahora
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  // Si el más grande no es la raíz
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];

    // Recursivamente heapify el subárbol afectado
    heapify(arr, n, largest);
  }
}

// Ejemplo de uso
const array = [12, 11, 13, 5, 6, 7];
console.log("Array ordenado:", heapSort(array));
                
            

Puntos Clave del Algoritmo

• Entrada: Un arreglo desordenado (arr).
• Salida: El arreglo ordenado de menor a mayor.
• Método:
  • Construye un max heap del arreglo para que el elemento más grande esté en la raíz.
  • Intercambia la raíz con el último elemento y reduce el tamaño del heap.
  • Reorganiza el heap (heapify) para mantener la propiedad de heap.
  • Repite hasta que el heap tenga un solo elemento.
• Complejidad:
  • Peor caso: O(n log n).
  • Mejor caso: O(n log n).
  • Promedio: O(n log n).
• Ventajas: Es in-place y no requiere espacio adicional significativo.
• Desventajas: No es un algoritmo estable, lo que significa que el orden relativo de los elementos iguales puede cambiar.

Ejemplo de Ejecución

Arreglo inicial: [12, 11, 13, 5, 6, 7]

Proceso de ordenamiento:

1. Construye el max heap: [13, 11, 12, 5, 6, 7].
2. Intercambia la raíz con el último elemento y reorganiza: [12, 11, 7, 5, 6, 13].
3. Continúa reduciendo el heap: [11, 7, 6, 5, 12, 13].
4. Últimos pasos hasta el arreglo ordenado: [5, 6, 7, 11, 12, 13].

Arreglo final ordenado: [5, 6, 7, 11, 12, 13]

Información Adicional

Heap Sort es un algoritmo confiable con una complejidad O(n log n), lo que lo hace adecuado para aplicaciones de ordenamiento en memoria limitada. Aunque no es estable, su eficiencia y simplicidad lo hacen una buena opción en sistemas donde no se necesita mantener el orden relativo de los elementos iguales.