HeapSort implementation in Javascript

Question

I am learning about heaps and I wanted to implement the heap sort algorithm in Javascript using MinHeap. The issue is that I keep getting a non-sorted array. I even tried to just translate a working algorithm from C++ to Javascript. Orginal algorithm link: https://www.geeksforgeeks.org/heap-sort-for-decreasing-order-using-min-heap/

C++:

// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
    int smallest = i; // Initialize smalles as root 
    int l = 2 * i + 1; // left = 2*i + 1 
    int r = 2 * i + 2; // right = 2*i + 2 


// 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) { 
    swap(arr[i], arr[smallest]); 

    // Recursively heapify the affected sub-tree 
    heapify(arr, n, smallest); 


 } 
} 



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

Javascipt (translated code):

    function swap(arr, i, j){
    const c = arr[i];
    arr[i] = arr[j];
    arr[j] = c;
}

function heapify(arr, n, i) 
{ 
    let smallest = i; // Initialize smalles as root 
    let l = 2 * i + 1; // left = 2*i + 1 
    let r = 2 * i + 2; // right = 2*i + 2 
  
    // 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) { 
        swap(arr[i], arr[smallest]); 
  
        // Recursively heapify the affected sub-tree 
        heapify(arr, n, smallest); 
    } 
} 
  
// main function to do heap sort 
function heapSort(arr, n) 
{ 
    // Build heap (rearrange array) 
    for (let i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
  
    // One by one extract an element from heap 
    for (let i = n - 1; i >= 0; i--) { 
        // Move current root to end 
        swap(arr[0], arr[i]); 
  
        // call max heapify on the reduced heap 
        heapify(arr, i, 0); 
    } 
} 

when I try with this array arr = [1,2,7,3,5], the heapSort algorithm returns this table [ 1, 2, 7, 3, 5 ];

Can you please help me figure out what's wrong with the JS implementation? thank you in advance!

Answer 1

const HeapSort = (arg) => {
  const Income_arr = [...arg];
  const Output_arr = [];

  const InnerSort = () => {
    const length = Income_arr.length;
    for (let i = 0; i < Income_arr.length - 1; i++) {
      let max = i;
      const left = i + 1;
      const right = i + 2;
      
      // will change '>' or '<' depends on which order we want, like either descending or ascending order
      
      if (i <= length && Income_arr[i] > Income_arr[left]) { 
        // swapping the array
        [Income_arr[i], Income_arr[left]] = [Income_arr[left], Income_arr[i]];
      }
      if (i <= length && Income_arr[i] > Income_arr[right]) {
         // swapping the array
        [Income_arr[i], Income_arr[right]] = [Income_arr[right], Income_arr[i]];
      }
    }
    Output_arr.push(Income_arr.shift()); // Add the largest Number in output_arr & remove the largest Number
    return Income_arr;
  };

  for (let i = arg.length - 1; i >= 0; i--) {
    // Run untill array length ends
    InnerSort(); // To Find the largest number
  }
  console.log(Output_arr)
  return Output_arr;
};


HeapSort([16, 20, 99, 34, 17, 15]);
HeapSort([16, 20, -99, 34, 17, 15]);
HeapSort([4, 20, 9, 34, 2, 15]);

const HeapSort = (arg) => {
  const Income_arr = [...arg];
  const Output_arr = [];

  const InnerSort = () => {
    const length = Income_arr.length;
    for (let i = 0; i < Income_arr.length - 1; i++) {
      let max = i;
      const left = i + 1;
      const right = i + 2;
      
      // will change '>' or '<' depends on which order we want, like either descending or ascending order
      
      if (i <= length && Income_arr[i] > Income_arr[left]) { 
        // swapping the array
        [Income_arr[i], Income_arr[left]] = [Income_arr[left], Income_arr[i]];
      }
      if (i <= length && Income_arr[i] > Income_arr[right]) {
         // swapping the array
        [Income_arr[i], Income_arr[right]] = [Income_arr[right], Income_arr[i]];
      }
    }
    Output_arr.push(Income_arr[length - 1]); // Add the largest Number in output_arr
    Income_arr.pop(); // Remove the largest Number
    return Income_arr;
  };

  for (let i = arg.length - 1; i >= 0; i--) {
    // Run untill array length ends
    InnerSort(); // To Find the largest number
  }
  console.log(Output_arr)
  return Output_arr;
};


HeapSort([16, 20, 99, 34, 17, 15]);
HeapSort([16, 20, -99, 34, 17, 15]);
HeapSort([4, 20, 9, 34, 2, 15]);

Answer 2

Here is my version of heapsort. This is non-recursive solution and modifies the original array.

function swap(arr, i, j) { 
    const tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp; 
}
function heapify(arr, start = 0) {  
    for(let i = start;i < arr.length; i++) {  
        let j = i;
        let root = start + Math.floor((j-start)/2);  
        while(( root >= start ) && (arr[root] < arr[j])) { 
            swap(arr, root, j); 
            j = root;
            root = start + Math.floor((j-start)/2);  
        }
    } 
}
function heapSort(arr) {  
    for(let i = 0; i < arr.length;i++) 
        heapify(arr, i);    
}

const arr = [1,2,8000,3,4,5,-1,200000,8000,-1,20000];
heapSort(arr);
console.log(arr); 

 

Answer 3

This code should go fine:

const heapify = (arr, length, i) => {
  let largest = i
  const left = i * 2 + 1
  const right = left + 1

  if (left < length && arr[left] > arr[largest]) {
    largest = left
  }

  if (right < length && arr[right] > arr[largest]) {
    largest = right
  }

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]]
    heapify(arr, length, largest)
  }

  return arr
}

const heapSort = arr => {
  const length = arr.length
  let i = Math.floor(length / 2 - 1)
  let k = length - 1

  while (i >= 0) {
    heapify(arr, length, i)
    i--
  }

  while (k >= 0) {
    [arr[0], arr[k]] = [arr[k], arr[0]]
    heapify(arr, k, 0)
    k--
  }

  return arr
}

const arr = [4, 6, 3, 2, 9];
sortedArr = heapSort(arr);

console.log("Sorted array is \n", sortedArr)

I took it from here. Take a look at the post if you are more interested in how it's implemented. It's very well explained.

UPDATE

Ok so, about your code, I see exactly 2 problems:

1. You are incorrectly using the "swap" function. Just change swap(arr[i], arr[smallest] by swap(arr, i, smallest); and swap(arr[0], arr[i]) by swap(arr, 0, i). Also, if you want to use the latest ES6 features you can swap elements in an array without implementing that "swap" function, just like this: [arr[0], arr[2]] = [arr[2], arr[0]] (this will swap the element at position 0 with the element at position 2). This is called destructuring assignment.
2. In the first for loop in your "heapSort" function, initialize i variable to an integer (notice that n / 2 could be a float). You can do it like this: let i = Math.floor(n / 2 - 1).

Here I leave you the fixed code. I've executed it by myself and it works:

function swap(arr, i, j){
  const c = arr[i];
  arr[i] = arr[j];
  arr[j] = c;
}

function heapify(arr, n, i) 
{ 
  let smallest = i; // Initialize smallest as root 
  let l = 2 * i + 1; // left = 2*i + 1 
  let r = 2 * i + 2; // right = 2*i + 2 

  // 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) { 
      swap(arr, i, smallest); 

      // Recursively heapify the affected sub-tree 
      heapify(arr, n, smallest); 
  } 
} 

// main function to do heap sort 
function heapSort(arr, n) 
{ 
  // Build heap (rearrange array) 
  for (let i = Math.floor(n / 2 - 1); i >= 0; i--) 
      heapify(arr, n, i); 

  // One by one extract an element from heap 
  for (let i = n - 1; i >= 0; i--) { 
      // Move current root to end 
      swap(arr, 0, i); 

      // call max heapify on the reduced heap 
      heapify(arr, i, 0); 
  } 
}

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

console.log("Sorted array is \n", arr)