Heap sort algorithm in Javascript

Learn what is Heap sort algorithm and how to implement it in Javascript.

List of sorting algorithm

• Bubble sort algorithm in javascript
• Insertion sort algorithm in javascript
• Selection sort in javascript
• Merge sort in javascript
• Quick sort in javascript
• Counting sort in javascript
• Radix sort in javascript
• Bucket sort in javascript
• Shell Sort in javascript

What is heap sort?

Invented by J.W.J Williams in 1964.

Heap sort is a comparison-based sorting algorithm. It can be considered as an improvised version of selection sort. Just like selection sort, heapsort divides the given input into sorted and unsorted regions and it keeps shrinking the unsorted region by removing the largest or the smallest element depending upon the order of sorting and keeps adding them in sorted region.

It is better than selection sort, because rather than wasting time on linear-time scan on the unsorted region, it maintains a heap data structure to find the largest or smallest element quickly.

It is an in-place sorting algorithm as it does not requires any extra space, but is not considered as a stable sort.

It is a tree based sort which takes an array as an input and convert it to a tree using certain formula.

---

Array to Tree conversion

A complete binary tree has an interesting property that we can use to find the children and parents of any node.

If the index of any element in the array is i, the element in the index 2i+1 will become the left child and element in 2i+2 index will become the right child. Also, the parent of any element at index i is given by the lower bound of (i-1)/2.

---

How heap sort works?

Heap sort works using heap data structure.

Heap is a special tree based data structure. A binary tree is said to follow a heap data structure if

1. It is a complete binary tree.
2. All nodes are either greater than or equal to or less than or equal to each of its children. If the parent nodes are greater than their child nodes, heap is called a Max-Heap, and if the parent nodes are smaller than their child nodes, heap is called Min-Heap.

The following image represents Max-Heap and Min-Heap.

First heapify the heap data structure to build the max or min heap depending upon the sorting order.

To build a max-heap from any tree, we can start heapifying each sub-tree from the bottom up and end up with a max-heap. Repeat this for all the elements including the root element.

In the case of a complete tree, the first index of a non-leaf node is given by n/2 - 1. All other nodes after that are leaf-nodes and thus don’t need to be heapified.

To sort in ascending order

• As the tree satisfies Max-Heap property, then the largest item is stored at the root node.
• Swap: Swap the first element with the last element.
• Remove: Remove the last element from the heap.
• Heapify: Heapify the root element again so that we have the highest element at root.
• Repeat this until all the items of the list are sorted.

Heapify(array, size, i)
  set i as largest
  leftChild = 2i + 1
  rightChild = 2i + 2
  
  if leftChild > array[largest]
    set leftChildIndex as largest
  if rightChild > array[largest]
    set rightChildIndex as largest

  swap array[i] and array[largest]

MaxHeap(array, size)
  loop from the first index of non-leaf node down to zero
    call heapify
  
  loop from the last index of array down to zero
    swap array[0] and array[i]
    call heapify

Heap sort algorithm in Javascript using Max-heap

const maxHeapify = (arr, n, i) => {
  let largest = i;
  let l = 2 * i + 1; //left child index
  let r = 2 * i + 2; //right child index
  
  //If left child is smaller than root
   if (l < n && arr[l] > arr[largest]) {
         largest = l; 
   }
  
   // If right child is smaller than smallest so far 
   if (r < n && arr[r] > arr[largest]) {
        largest = r; 
   }
  
   // If smallest is not root 
   if (largest != i) { 
        let temp = arr[i]; 
        arr[i] = arr[largest]; 
        arr[largest] = temp; 
  
      // Recursively heapify the affected sub-tree 
      maxHeapify(arr, n, largest); 
    } 
}

 // main function to do heap sort 
 const heapSort = (arr, n) => { 
     // Build heap (rearrange array) 
     for (let i = parseInt(n / 2 - 1); i >= 0; i--) {
         maxHeapify(arr, n, i); 
     }
  
     // One by one extract an element from heap 
     for (let i = n - 1; i >= 0; i--) { 
        // Move current root to end 
        let temp = arr[0]; 
        arr[0] = arr[i]; 
        arr[i] = temp; 
  
        // call max heapify on the reduced heap 
        maxHeapify(arr, i, 0); 
     } 
 }

Input:
const arr = [4, 6, 3, 2, 9];
heapSort(arr, arr.length);
console.log(arr);

Output:
[2, 3, 4, 6, 9]

Sort in descending order using Heap sort and Min-heap

const minHeapify = (arr, n, i) => {
  let smallest = i;
  let l = 2 * i + 1; //left child index
  let r = 2 * i + 2; //right child index
  
  //If left child is smaller than root
   if (l < n && arr[l] < arr[smallest]) {
            smallest = l; 
   }
  
   // If right child is smaller than smallest so far 
   if (r < n && arr[r] < arr[smallest]) {
        smallest = r; 
   }
  
   // If smallest is not root 
   if (smallest != i) { 
        let temp = arr[i]; 
        arr[i] = arr[smallest]; 
        arr[smallest] = temp; 
  
      // Recursively heapify the affected sub-tree 
      minHeapify(arr, n, smallest); 
    } 
}

 // main function to do heap sort 
 const heapSort = (arr, n) => { 
     // Build heap (rearrange array) 
     for (let i = parseInt(n / 2 - 1); i >= 0; i--) {
         minHeapify(arr, n, i); 
     }
  
     // One by one extract an element from heap 
     for (let i = n - 1; i >= 0; i--) { 
        // Move current root to end 
        let temp = arr[0]; 
        arr[0] = arr[i]; 
        arr[i] = temp; 
  
        // call max heapify on the reduced heap 
        minHeapify(arr, i, 0); 
     } 
 }

Input:
const arr = [4, 6, 3, 2, 9];
heapSort(arr, arr.length);
console.log(arr);

Output:
[9, 6, 4, 3, 2]

Heap sort time complexity

Max-heapify has complexity O(logn) , Build heap has complexity O(n) and we run Max-heapify O(n) times in Heap sort function, Thus complexity of heap_sort is O(nlogn) + O(nlogn) = O(nlogn).

Heap sort space complexity

As heap sort is an in-place sorting algorithm it requires O(1) space.