How To Do Heap Sort in JavaScript

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It is an in-place, non-recursive algorithm that requires no additional memory apart from the input array and performs the sorting directly on the array. In this post, we’ll go over the JavaScript implementation of Heap Sort and its time and space complexities and explain how the algorithm works step by step.

What is Heap Sort?

Heap Sort leverages the properties of a binary heap to sort an array. The binary heap is a special kind of complete binary tree where the parent nodes are either greater than or equal to (max-heap) or less than or equal to (min-heap) their child nodes.

Heap Sort typically works with a max-heap. It sorts an array by first building a max-heap from the unsorted array and then repeatedly extracting the maximum element from the heap and placing it at the end of the array.

Pseudocode for Heap Sort

Here’s the pseudocode for Heap Sort:

procedure heapSort(arr)
    n = length(arr)
    
    // Step 1: Build the max-heap
    for i = n / 2 - 1 down to 0 do
        heapify(arr, n, i)

    // Step 2: Extract elements from the heap
    for i = n - 1 down to 1 do
        swap arr[0] with arr[i]   // Move the current largest to the end
        heapify(arr, i, 0)        // Heapify the reduced heap

procedure heapify(arr, n, i)
    largest = i                  // Initialize largest as the root
    left = 2 * i + 1             // Left child
    right = 2 * i + 2            // Right child

    if left < n and arr[left] > arr[largest] then
        largest = left           // If left child is larger

    if right < n and arr[right] > arr[largest] then
        largest = right          // If right child is larger

    if largest != i then
        swap arr[i] with arr[largest]
        heapify(arr, n, largest)  // Recursively heapify the affected sub-tree

• Step-by-Step Explanation:
  • Build the max-heap: Rearrange the array to satisfy the max-heap property.
  • Extract the max element: Swap the root (largest element) with the last element, reduce the heap size, and heapify the reduced heap.

Time Complexity of Heap Sort

• Best Case: O(n log n) – Building the heap takes O(n) time, and extracting the elements (heapify) takes O(log n) for each element. Since there are n elements, the total complexity is O(n log n).
• Average Case: O(n log n) – Similar to the best case, heap construction and repeated heapify operations lead to O(n log n) complexity.
• Worst Case: O(n log n) – Heap Sort’s worst-case performance is O(n log n) in all cases, making it a very consistent algorithm.

Space Complexity of Heap Sort

• Space Complexity: O(1) – Heap Sort is an in-place sorting algorithm, meaning it sorts the array without requiring additional space (apart from a few variables).

JavaScript Implementation of Heap Sort

Here’s how you can implement Heap Sort in JavaScript:

// Function to heapify a subtree rooted at index i in array of size n
function heapify(arr, n, i) {
    let largest = i;         // Initialize largest as root
    let left = 2 * i + 1;    // Left child
    let right = 2 * i + 2;   // Right child

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // If right child is larger than the largest so far
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // If largest is not root
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];  // Swap
        
        // Recursively heapify the affected subtree
        heapify(arr, n, largest);
    }
}

// Main function to implement Heap Sort
function heapSort(arr) {
    let n = arr.length;

    // Step 1: Build max-heap
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Step 2: Extract elements from the heap one by one
    for (let i = n - 1; i > 0; i--) {
        // Move the current root to the end
        [arr[0], arr[i]] = [arr[i], arr[0]];
        
        // Heapify the reduced heap
        heapify(arr, i, 0);
    }
}

// Example usage
const arr = [12, 11, 13, 5, 6, 7];
console.log("Initial array:", arr);
heapSort(arr);
console.log("Sorted array:", arr);

Output:

Initial array: [ 12, 11, 13, 5, 6, 7 ]
Sorted array: [ 5, 6, 7, 11, 12, 13 ]

Explanation:

• The heapify() function ensures that the subtree rooted at index i satisfies the max-heap property.
• The heapSort() function first builds a max-heap and repeatedly extracts the largest element by swapping the root with the last element and heapifying the reduced array.

Step-by-Step Walkthrough of Heap Sort

Let’s walk through Heap Sort using the array [12, 11, 13, 5, 6, 7].

Step 1: Build the Max-Heap

• Start from the middle of the array (non-leaf nodes) and heapify each subtree.
  • Heapify at index 2: [12, 11, 13, 5, 6, 7] (13 is already the max in its subtree).
  • Heapify at index 1: [12, 11, 13, 5, 6, 7] (11 is smaller than 13, so no change).
  • Heapify at index 0: [13, 11, 12, 5, 6, 7] (13 is the largest element).

Step 2: Swap the Root and Heapify

• Swap the root (largest element) with the last element and reduce the heap size by 1.
  • Swap and heapify: [7, 11, 12, 5, 6, 13] → heapify to [12, 11, 7, 5, 6, 13].
  • Swap and heapify: [6, 11, 7, 5, 12, 13] → heapify to [11, 6, 7, 5, 12, 13].
  • Continue this process until the array is sorted.

Pros and Cons of Using Heap Sort

Pros:

1. Efficient for Large Datasets: With a time complexity of O(n log n), Heap Sort is highly efficient for large datasets.
2. In-Place Sorting: Heap Sort sorts the array in place, using constant extra space (O(1)).
3. Consistent Performance: Unlike Quick Sort, which can degrade to O(n²) in the worst case, Heap Sort guarantees O(n log n) time complexity even in the worst case.

Cons:

1. Not Stable: Heap Sort is not a stable sorting algorithm, meaning the relative order of equal elements is not preserved.
2. More Comparisons: Compared to Quick Sort or Merge Sort, Heap Sort may perform more comparisons, making it slightly slower in practice despite having the same time complexity.

When to Use Heap Sort

Heap Sort is a good choice when:

1. You need guaranteed O(n log n) performance: Unlike Quick Sort, Heap Sort always performs in O(n log n), even in the worst case.
2. In-Place Sorting: Since Heap Sort requires only O(1) extra space, it’s ideal for memory-constrained environments.
3. You need a simple, non-recursive algorithm: Heap Sort doesn’t require complex recursion, making it suitable for systems with limited stack space.

However, due to the larger number of comparisons, Heap Sort may be slightly slower than Quick Sort or Merge Sort in practice, making it less common for general-purpose sorting.

Optimizing Heap Sort

1. Use an Iterative Version of Heapify: The recursive heapify() function can lead to deeper stack calls for large datasets. Converting it into an iterative version reduces the overhead of recursion and improves memory usage.
2. Optimized Build-Heap Process: The heap-building step takes O(n) time, but there are ways to minimize the overhead. For example, starting the heapify process from the middle of the array (non-leaf nodes) ensures fewer comparisons and quicker heap construction.
3. Reduced Number of Swaps: By delaying swaps and using a single swap after the heapify process, you can reduce the number of costly swap operations in Heap Sort. This optimization can be especially beneficial when sorting large datasets.
4. Hybrid Algorithms: In scenarios involving small subarrays, switching to a simpler algorithm like Insertion Sort for small segments (as in IntroSort) can improve performance.

Conclusion

Heap Sort is an efficient, in-place sorting algorithm with a guaranteed O(n log n) time complexity, even in the worst case. While it isn’t stable and may involve more comparisons than other algorithms, it remains reliable when consistency and minimal space usage are required.

Congratulations on reading to the end of the tutorial!

Read the following articles to learn how to implement Heap Sort:

In Python – How to do Heap Sort in Python

In C++ – How to Do Heap Sort in C++

Have fun and happy researching!