JavaScript Implementation of Min Heap

Question

JavaScript Implementation of Min Heap

Hello! I've been working on implementing a min heap in JavaScript and I have a question about the removeMin algorithm. I am using an array to store the heap internally. When percolating downwards, I am currently using the condition 2 * k <= this.size as the stopping point. However, it doesn't feel quite right to me. Do you have any suggestions for a better stopping condition? Thank you in advance for your help!

this.removeMin = function () {
    //replace root with last element and percolate downwards
    var min = this._heap[1],
        k,
        left,
        right;

    this._heap[1] = this._heap.pop();
    this.size--;
    k = 1;

    while ( ( 2 * k ) <= this.size) {
        left = 2 * k;
        right = 2 * k + 1;

        if (this._heap[k] > this._heap[left] && this._heap[k] > this._heap[right]) {
            if (this._heap[left] <= this._heap[right]) {
                swap(this._heap, k, left);
                k = left;
            } else {
                swap(this._heap, k, right);
                k = right;
            }
        } else if (this._heap[k] > this._heap[left]) {
            swap(this._heap, k, left);
            k = left;
        } else {
            swap(this._heap, k, right);
            k = right;
        }
    }

    return min;
};

javascript algorithm heap min-heap

Answer 1

Answer №1

This is a simpler approach that may provide some assistance.

class MinHeap {
  constructor(array) {
    this.heap = this.buildHeap(array);
  }

  // O(n) time | O(1) space
  buildHeap(array) {
    const firstParentIdx = Math.floor((array.length - 2) / 2);
    for (let currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
      this.siftDown(currentIdx, array.length - 1, array);
    }
    return array;
  }

  // O(log(n)) time | O(1) space
  siftDown(currentIdx, endIdx, heap) {
    let childOneIdx = currentIdx * 2 + 1;
    while (childOneIdx <= endIdx) {
      const childTwoIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
      let idxToSwap;
      if (childTwoIdx !== -1 && heap[childTwoIdx] < heap[childOneIdx]) {
        idxToSwap = childTwoIdx;
      } else {
        idxToSwap = childOneIdx;
      }

      if (heap[idxToSwap] < heap[currentIdx]) {
        this.swap(currentIdx, idxToSwap, heap);
        currentIdx = idxToSwap;
        childOneIdx = currentIdx * 2 + 1;
      } else {
        return;
      }
    }
  }

  // O(log(n)) time | O(1) space
  siftUp(currentIdx, heap) {
    let parentIdx = Math.floor((currentIdx - 1) / 2);
    while (currentIdx > 0 && heap[currentIdx] < heap[parentIdx]) {
     this.swap(currentIdx, parentIdx, heap);
      currentIdx = parentIdx;
      parentIdx = Math.floor((currentIdx - 1) / 2);
    }
  }

  // O(1)  time | O(1) space
  peek() {
    return this.heap[0];
  }

  // O(log(n)) time | O(1) space
  remove() {
    this.swap(0, this.heap.length - 1, this.heap);
    const valueToRemove = this.heap.pop();
    this.siftDown(0, this.heap.length - 1, this.heap);
    return valueToRemove;
  }

  // O(log(n)) time | O(1) space
  insert(value) {
    this.heap.push(value);
    this.siftUp(this.heap.length - 1, this.heap);
  }

  swap(i, j, heap) {
    [heap[i], heap[j]] = [heap[j], heap[i]];
  }
}

Answer 2

This is a simpler approach that may provide some assistance.

class MinHeap {
  constructor(array) {
    this.heap = this.buildHeap(array);
  }

  // O(n) time | O(1) space
  buildHeap(array) {
    const firstParentIdx = Math.floor((array.length - 2) / 2);
    for (let currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
      this.siftDown(currentIdx, array.length - 1, array);
    }
    return array;
  }

  // O(log(n)) time | O(1) space
  siftDown(currentIdx, endIdx, heap) {
    let childOneIdx = currentIdx * 2 + 1;
    while (childOneIdx <= endIdx) {
      const childTwoIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
      let idxToSwap;
      if (childTwoIdx !== -1 && heap[childTwoIdx] < heap[childOneIdx]) {
        idxToSwap = childTwoIdx;
      } else {
        idxToSwap = childOneIdx;
      }

      if (heap[idxToSwap] < heap[currentIdx]) {
        this.swap(currentIdx, idxToSwap, heap);
        currentIdx = idxToSwap;
        childOneIdx = currentIdx * 2 + 1;
      } else {
        return;
      }
    }
  }

  // O(log(n)) time | O(1) space
  siftUp(currentIdx, heap) {
    let parentIdx = Math.floor((currentIdx - 1) / 2);
    while (currentIdx > 0 && heap[currentIdx] < heap[parentIdx]) {
     this.swap(currentIdx, parentIdx, heap);
      currentIdx = parentIdx;
      parentIdx = Math.floor((currentIdx - 1) / 2);
    }
  }

  // O(1)  time | O(1) space
  peek() {
    return this.heap[0];
  }

  // O(log(n)) time | O(1) space
  remove() {
    this.swap(0, this.heap.length - 1, this.heap);
    const valueToRemove = this.heap.pop();
    this.siftDown(0, this.heap.length - 1, this.heap);
    return valueToRemove;
  }

  // O(log(n)) time | O(1) space
  insert(value) {
    this.heap.push(value);
    this.siftUp(this.heap.length - 1, this.heap);
  }

  swap(i, j, heap) {
    [heap[i], heap[j]] = [heap[j], heap[i]];
  }
}

Answer 3

Answer №2

In my opinion, it appears that there is a missing condition in the code. If the value of element k is greater than both the left and right elements, the downward movement should halt. The revised code should look like this:

   if (this._heap[k] > this._heap[left] && this._heap[k] > this._heap[right]) {
        if (this._heap[left] <= this._heap[right]) {
            swap(this._heap, k, left);
            k = left;
        } else {
            swap(this._heap, k, right);
            k = right;
        }
    } else if (this._heap[k] > this._heap[left]) {
        swap(this._heap, k, left);
        k = left;
    } else if(this._heap[k] < this._heap[right]) {
        swap(this._heap, k, right);
        k = right;
    } else {
        break;
    }

Answer 4

In my opinion, it appears that there is a missing condition in the code. If the value of element k is greater than both the left and right elements, the downward movement should halt. The revised code should look like this:

   if (this._heap[k] > this._heap[left] && this._heap[k] > this._heap[right]) {
        if (this._heap[left] <= this._heap[right]) {
            swap(this._heap, k, left);
            k = left;
        } else {
            swap(this._heap, k, right);
            k = right;
        }
    } else if (this._heap[k] > this._heap[left]) {
        swap(this._heap, k, left);
        k = left;
    } else if(this._heap[k] < this._heap[right]) {
        swap(this._heap, k, right);
        k = right;
    } else {
        break;
    }

Answer 5

Answer №3

Avoid repetitive coding by referring to the following optimized code snippet instead of writing comparison code repeatedly. You can enhance your code by replacing it with a while loop.

.....
while (2 * k <= this.size) {
        let j = 2 * key;
        if (j < this.size && less(j, j + 1)) j++; // find smallest child
        if (!less(k, j)) break; // ensure parent is smaller than smallest child
        exch(k, j); // swap if parent is larger
        k = j; // continue until reaching the end (this.size)
    }
.....
function less(i, j){
    return this._heap[j] < this._heap[i];
}
function exch(i, j){
    let temp = this._heap[i];
    this._heap[i] = this._heap[j];
    this._heap[j] = temp;
}

Give it a try and see if it improves your code efficiency.

Answer 6

Avoid repetitive coding by referring to the following optimized code snippet instead of writing comparison code repeatedly. You can enhance your code by replacing it with a while loop.

.....
while (2 * k <= this.size) {
        let j = 2 * key;
        if (j < this.size && less(j, j + 1)) j++; // find smallest child
        if (!less(k, j)) break; // ensure parent is smaller than smallest child
        exch(k, j); // swap if parent is larger
        k = j; // continue until reaching the end (this.size)
    }
.....
function less(i, j){
    return this._heap[j] < this._heap[i];
}
function exch(i, j){
    let temp = this._heap[i];
    this._heap[i] = this._heap[j];
    this._heap[j] = temp;
}

Give it a try and see if it improves your code efficiency.

JavaScript Implementation of Min Heap

Answer №1

Answer №2

Answer №3

Similar questions

Assign a title property in Vuejs only if the returned data from binding evaluates to true

JavaScript/DOM - What sets apart a "CSS Selector" from an attribute?

The changes made to the state array in react.js are not reflected in the DOM

Error message in node.bcrypt.js: 'No callback function provided; result is undefined.'

Executing jQuery AJAX with PHP using 'POST' method to receive and process PHP code

Sending an array as JSON data to PHP using the $.ajax post method. The $_POST array is

Error: The function react__WEBPACK_IMPORTED_MODULE_6___default.a.useState is not defined as a function

Show a selection of assorted files stored in the database

The JSON output from the gapi (Google Analytics) array in PHP is not displaying any values

Refreshing and enhancing Android contacts through the Expo project

Can someone provide a description for a field within typedoc documentation?

Calculating the frequency of a variable within a nested object in an Angular application

Although my service worker's IndexedDB add() operation was successful, I am unable to view the data in the Chrome dev tools Application/Storage section

Struggling to Load: Ajax Request to Google App Engine Causing Page to

What steps do I need to follow in order to properly execute this HTTP request?

How can I make a variable available on the client side by exporting it from my Node JS server built with express framework?

Obtain a fresh SQL identifier post submission through Ajax

Revolutionizing user experience: New feature seamlessly triggers button actions with the power of "enter"

Navigating through playlists on Ionic

Puzzled by the unexpected error I encountered while using Node.js (require.js)