CODEWITHSUNDEEP
javascriptalgorithm
Oumaima
Oumaima

Reputation: 594

Recursive maxHeap implementation in Javascript

I have been reading about heaps and seeing various implementations in javascript. https://codepen.io/beaucarnes/pen/JNvENQ?editors=0010 is a good example of insertion and removal. However, I want to write the building of a max heap in a recursive way. For example, in C++, the following code should do the trick:


// C++ program for building Heap from Array 
  
#include <iostream> 
  
using namespace std; 
  
// 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 largest = i; // Initialize largest as root 
    int l = 2 * i + 1; // left = 2*i + 1 
    int r = 2 * i + 2; // right = 2*i + 2 
  
    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 
  
    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
  
    // If largest is not root 
    if (largest != i) { 
        swap(arr[i], arr[largest]); 
  
        // Recursively heapify the affected sub-tree 
        heapify(arr, n, largest); 
    } 
} 
  
// Function to build a Max-Heap from the given array 
void buildHeap(int arr[], int n) 
{ 
    // Index of last non-leaf node 
    int startIdx = (n / 2) - 1; 
  
    // Perform reverse level order traversal 
    // from last non-leaf node and heapify 
    // each node 
    for (int i = startIdx; i >= 0; i--) { 
        heapify(arr, n, i); 
    } 
}

source: https://www.geeksforgeeks.org/building-heap-from-array/ The problem is that when I translate it to javascript:

function build_max_heap( A, n) {
        let start_index = Math.floor(n/2);
        for (let i=start_index; i>=0; i--){
                heapify(A, n, i);
        }
}

function heapify(A, n, i){
        let left = 2 * i;
        let right = 2 * i + 1;
        let largest = i;

        if (A[left] > A[largest]) largest = left;
        if (A[right] > A[largest]) largest = right;
        if(largest !== i) swap(A[i], A[largest]);

        heapify(A, n, largest)

}

function swap (A, x, y){
        let c = x;
        x = y;
        y = c;
}

I get this error:

VM56:2 Uncaught RangeError: Maximum call stack size exceeded
    at heapify (<anonymous>:2:20)
    at heapify (<anonymous>:10:9)
    at heapify (<anonymous>:10:9)
    at heapify (<anonymous>:10:9)
    at heapify (<anonymous>:10:9)
    at heapify (<anonymous>:10:9)
    at heapify (<anonymous>:10:9)
    at heapify (<anonymous>:10:9)
    at heapify (<anonymous>:10:9)
    at heapify (<anonymous>:10:9)
    ```

Can anyone help me figure out what's wrong with my implementation?

Upvotes: 1

Views: 202

Answers (1)

trincot
trincot

Reputation: 349946

Several issues:

(1) You have an error in this part:

let left = 2 * i;
let right = 2 * i + 1;

This is not correct. Imagine the index of the root, which is i=0, what will be the value of left? Again 0... that can't be right. The correct formula is in the code you quoted earlier:

let left = 2 * i + 1;
let right = 2 * i + 2;

(2) A second error occurs in the line where you call swap. You don't pass the right arguments. It expects 3: A and then two indices. You are passing two values. It should be (see also next point):

swap(A, i, largest);

(3) And then the swap function has a wrong implementation (JavaScript has only call by value). Changing x or y inside that function has no effect on the array. It should be like this:

function swap (A, x, y){
    let c = A[x];
    A[x] = A[y];
    A[y] = c;
}

(4) Finally, the recursive heapify function call should only be made if a swap is made:

if(largest !== i) {
    swap(A, i, largest);
    heapify(A, n, largest)
}

Corrected code in snippet:

function build_max_heap( A, n) {
    let start_index = Math.floor(n/2);
    for (let i=start_index; i>=0; i--){
        heapify(A, n, i);
    }
}

function heapify(A, n, i){
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let largest = i;
 
    if (A[left] > A[largest]) largest = left;
    if (A[right] > A[largest]) largest = right;
    if(largest !== i) {
        swap(A, i, largest);
        heapify(A, n, largest)
    }
}

function swap (A, x, y) {
    let c = A[x];
    A[x] = A[y];
    A[y] = c;
}

// example call
let A = [4, 3, 2, 1, 5, 9, 8, 7, 6];
build_max_heap(A, A.length);
console.log(A.join());

Upvotes: 1

Related Questions