Min heap in javascript

Question

Hey I tried to implement a min heap in javascript, but i had a question regarding the algorithm for remove min. I'm using an array to represent the heap internally. When I'm percolating downwards, what should be the stopping condition? In my code I have it at 2 * k <= this.size so it would travel down to potentially the very last element, but it doesn't feel "correct", is there a better stopping condition? Thanks in advance!

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;
};

Why? The index basically doubles every step, so you should get there in O(log n) — Stefan Haustein
– Stefan Haustein, Commented Mar 14, 2016 at 1:51
I think this is the correct condition. As you are checking with a number of elements inserted into the array, not with array length. — Prasanna
– Prasanna, Commented Jun 6, 2020 at 17:17

Wesam Mustafa · Accepted Answer · 2022-06-21 18:27:23Z

This is a much easier implementation, I hope this can help.

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

Yanhui Zhou · Accepted Answer · 2016-03-14 02:22:08Z

1

I think you miss one if condition. When the k element is both less than the right and the left, the downwards must stop. It must be:

   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;
    }

answered Mar 14, 2016 at 2:22

Yanhui Zhou

8989 silver badges21 bronze badges

Comments

Prasanna · Accepted Answer · 2020-06-06 17:30:26Z

Why you are writing compare code again and again. Sharing below code for reference which will optimize your code, you can replace it with your 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; // check parent is lesser than smallest child or not
        exch(k, j); //if parent is bigger then exchange
        k = j; //keep checking untill reaches to the end(this.size)
    }
.....
function less(i, j){
    if(this._heap[j] < this._heap[i] < 0) return true;
    else return false;
}
function exch(i, j){
    let temp = this._heap[i];
    this._heap[i] = this._heap[j];
    this._heap[j] = temp;
}

Hope this works.

Collectives™ on Stack Overflow

Min heap in javascript

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related