3

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!

Improve this question

3 Answers 3

Reset to default
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)
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

thank you! The article is great but the issue is that I still didn't figure out what's wrong with my algorithm and why the exact one seems to be working in C++ while it doesn't in Javascript (I also wanted to see heapSort in action with a minHeap) thank you though!
1

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);
Improve this answer

2 Comments

in heapSort you could improve by changing i < arr.length to i <= Math.floor(arr.length / 2 - 1). The leaves don't need to be sorted, so it stops at the last parent.
Did this in a very quick manner. Will check on this part.
0 

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]);

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.