**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**:

**Efficient for Large Datasets**: With a time complexity of O(n log n), Heap Sort is highly efficient for large datasets.**In-Place Sorting**: Heap Sort sorts the array in place, using constant extra space (O(1)).**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**:

**Not Stable**: Heap Sort is not a stable sorting algorithm, meaning the relative order of equal elements is not preserved.**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:

**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.**In-Place Sorting**: Since Heap Sort requires only O(1) extra space, it’s ideal for memory-constrained environments.**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**

**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.**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.**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.**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!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.