Understanding Heap Sort Algorithm in JavaScript

Introduction:

Sorting algorithms play a crucial role in computer science and programming. One such algorithm is Heap Sort, known for its efficiency and ability to handle large datasets. In this article, we will delve into the Heap Sort algorithm and implement it using JavaScript. By the end, you will have a clear understanding of how Heap Sort works and how to apply it to your own JavaScript projects.


What is Heap Sort?

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It divides the input array into a sorted region and an unsorted region, gradually expanding the sorted region by extracting the maximum element from the heap and placing it at the end of the sorted region. The algorithm repeats this process until the entire array is sorted.


Implementing Heap Sort in JavaScript:

To implement Heap Sort in JavaScript, we'll follow these steps:


Step 1: Build the Heap

Convert the input array into a max heap. Start from the first non-leaf node and compare it with its children, swapping if necessary to maintain the heap property.


Step 2: Extract Max and Heapify

  • Extract the maximum element from the heap and swap it with the last element of the unsorted region.
  • Heapify the remaining heap to restore the heap property.


Step 3: Repeat Until Sorted

  • Repeat the extract max and heapify process until the entire array is sorted. The sorted elements will accumulate at the end of the array.


3. Heap Sort JavaScript Implementation Example:

Let's take a look at a JavaScript implementation of the Heap Sort algorithm:


Code:


function heapSort(array) {

  const len = array.length;


  // Build max heap

  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {

    heapify(array, len, i);

  }


  // Extract max and heapify

  for (let i = len - 1; i >= 0; i--) {

    // Swap root (maximum element) with the last element

    [array[0], array[i]] = [array[i], array[0]];


    // Heapify the reduced heap

    heapify(array, i, 0);

  }


  return array;

}


function heapify(array, len, root) {

  let largest = root;

  const left = 2 * root + 1;

  const right = 2 * root + 2;


  if (left < len && array[left] > array[largest]) {

    largest = left;

  }


  if (right < len && array[right] > array[largest]) {

    largest = right;

  }


  if (largest !== root) {

    [array[root], array[largest]] = [array[largest], array[root]];

    heapify(array, len, largest);

  }

}


// Usage example

const unsortedArray = [7, 3, 9, 2, 1, 5];

const sortedArray = heapSort(unsortedArray);

console.log(sortedArray); // Output: [1, 2, 3, 5, 7, 9]




4. Analysis of Heap Sort:

  • Time Complexity: The time complexity of Heap Sort is O(n log n), making it efficient for large datasets.
  • Space Complexity: Heap Sort has a space complexity of O(1) since it operates directly on the input array.


Conclusion:

Heap Sort is a powerful sorting algorithm that utilizes the binary heap data structure to efficiently sort elements. By following the step-by-step guide and implementing the Heap Sort algorithm using JavaScript, you can easily sort arrays of any size. Understanding algorithms like Heap Sort empowers you to optimize performance in your JavaScript applications and solve complex sorting problems efficiently.