Implementing Heap Sort in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort an array in ascending or descending order. It is an in-place sorting algorithm, meaning that it does not require any additional space to sort the array.

The basic idea behind heap sort is to first create a heap from the input array, and then repeatedly remove the maximum (or minimum) element from the heap and add it to the sorted array. This process continues until the heap is empty, at which point the sorted array is returned.

There are two types of heaps: max heaps and min heaps. In a max heap, the value of each node is greater than or equal to the values of its children. In a min heap, the value of each node is less than or equal to the values of its children.

To create a heap from an array, we can start by inserting each element into the heap one at a time. For each element, we first add it to the end of the heap and then “heapify” it by swapping it with its parent until it is in the correct position.

Here is an example of how to create a max heap in JavaScript:

function createHeap(array) {
  // Create a heap from the input array
  let heap = [...array];
  // Starting from the last non-leaf node, heapify each node
  for (let i = Math.floor(heap.length / 2); i >= 0; i--) {
    heapify(heap, i, heap.length);
  }
  return heap;
}

function heapify(heap, i, heapSize) {
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  let largest = i;
  if (left < heapSize && heap[left] > heap[largest]) {
    largest = left;
  }
  if (right < heapSize && heap[right] > heap[largest]) {
    largest = right;
  }
  if (largest !== i) {
    [heap[i], heap[largest]] = [heap[largest], heap[i]];
    heapify(heap, largest, heapSize);
  }
}

let array = [3, 5, 1, 4, 2];
let heap = createHeap(array);
// heap is now [5, 4, 2, 3, 1]

To sort the array using heap sort, we can simply remove the maximum element from the heap and add it to the sorted array until the heap is empty.

Here is an example of how to perform heap sort in JavaScript:

function heapSort(array) {
  let heap = createHeap(array);
  let sortedArray = [];
  while (heap.length > 0) {
    // Remove the maximum element from the heap and add it to the sorted array
    sortedArray.unshift(heap.shift());
    // Re-heapify the remaining elements
    heap = createHeap(heap);
  }
  return sortedArray;
}

let array = [3, 5, 1, 4, 2];
let sortedArray = heapSort(array);
// sortedArray is now [1, 2, 3, 4, 5]

Heap sort is an efficient sorting algorithm that is suitable for large data sets. It has a time complexity of O(n log n), making it faster than other comparison-based sorting algorithms such as bubble sort and insertion sort. However, it is not a stable sort.

I founded Higglo Digital and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a beautifully designed website, check us out.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!