Iterative heap sort in Javascript

We have already seen what is the heap sort algorithm and how to implement it recursively in Javascript. In this example, we will see the iterative implementation of it.

Example

Input:
[10, 20, 15, 17, 9, 21]

Output:
[21, 20, 17, 15, 10, 9]

HeapSort is a comparison-based in-place sorting technique where we first build Max Heap and then swaps the root element with the last element and maintains the heap property each time to finally make it sorted.

Iterative heap sort in javascript to sort in descending order.

To sort the list in descending order we have to min-heapify the list for each element of the array and then perform the following actions on it.

• As the tree satisfies the Min-Heap property, then the smallest 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 on the list are sorted.

const minHeapify = (arr, n) => {
  for(let i = 1; i < n; i++){
    //If child is greater than parent
    if(arr[i] < arr[parseInt((i - 1) / 2)]){
      let j = i;
      
      // swap child and parent until 
      // parent is smaller
      while (arr[j] < arr[parseInt((j - 1) / 2)]) {
          //Get the indexes of both the child
          const l = j;
          const r = parseInt((j - 1) / 2);
          
          //Swap
          [arr[l], arr[r]] = [arr[r], arr[l]];
          
          //reduce
          j = parseInt((j - 1) / 2); 
      } 
    }
  }
}

const heapSort = (arr, n = arr.length) => {
  minHeapify(arr, n);
  
  for(let i = n - 1; i > 0; i--){
    // swap value of first indexed 
    // with last indexed 
    [arr[0], arr[i]] = [arr[i], arr[0]]; 
  
    // maintaining heap property 
    // after each swapping 
    let j = 0, index; 
    
    do { 
        index = (2 * j + 1); 
  
        // if left child is smaller than 
        // right child point index variable 
        // to right child 
        if (index < (i - 1) && arr[index] > arr[index + 1]) {
          index++; 
        }
  
        // if parent is smaller than child 
        // then swapping parent with child 
        // having higher value 
        if (index < i && arr[j] > arr[index]) {
          [arr[j], arr[index]] = [arr[index], arr[j]];
        }
      
        j = index; 
      } while (index < i); 
  }
}

Input:
const arr = [10, 20, 15, 17, 9, 21];
heapSort(arr);
console.log(arr);

Output:
[21, 20, 17, 15, 10, 9]

---

Iterative heap sort in javascript to sort in ascending order.

To sort in ascending order we build the Max-Heap and then repeat the same process as above.

const maxHeapify = (arr, n) => {
  for(let i = 1; i < n; i++){
    //If child is greater than parent
    if(arr[i] > arr[parseInt((i - 1) / 2)]){
      let j = i;
      
      // swap child and parent until 
      // parent is smaller
      while (arr[j] > arr[parseInt((j - 1) / 2)]) {
          //Get the indexes of both the child
          const l = j;
          const r = parseInt((j - 1) / 2);
          
          //Swap
          [arr[l], arr[r]] = [arr[r], arr[l]];
          
          //reduce
          j = parseInt((j - 1) / 2); 
      } 
    }
  }
}

const heapSort = (arr, n = arr.length) => {
  maxHeapify(arr, n);
  
  for(let i = n - 1; i > 0; i--){
    // swap value of first indexed 
    // with last indexed 
    [arr[0], arr[i]] = [arr[i], arr[0]]; 
  
    // maintaining heap property 
    // after each swapping 
    let j = 0, index; 
    
    do { 
        index = (2 * j + 1); 
  
        // if left child is smaller than 
        // right child point index variable 
        // to right child 
        if (index < (i - 1) && arr[index] < arr[index + 1]) {
          index++; 
        }
  
        // if parent is smaller than child 
        // then swapping parent with child 
        // having higher value 
        if (index < i && arr[j] < arr[index]) {
          [arr[j], arr[index]] = [arr[index], arr[j]];
        }
      
        j = index; 
      } while (index < i); 
  }
}

Input:
const arr = [10, 20, 15, 17, 9, 21];
heapSort(arr);
console.log(arr);

Output:
[9, 10, 15, 17, 20, 21]

Time complexity: O(nlogn).
Space complexity: O(1).