Implementing a Min Heap in Javascript?

user_8418879 0
Viewed 218

I'm having trouble with one of my test cases and I can't figure out why. Any help would be appreciated. I tried implementing a min-heap with number types but something seems to be off. I tried to make the class as clear as possible. The expected order for a min-heap should be in ascending order when removing elements, for example: 1,2,3,4,5,6.

Min Heap Class:

class MinHeap {
  
  constructor() {
    this.heap = [];
  }
  
  getLeftChildIndex(parentIndex) { return 2 * parentIndex + 1; }
  getRightChildIndex(parentIndex) { return 2 * parentIndex + 2; }
  getParentIndex(childIndex) { return Math.floor((childIndex - 1) / 2); }
    
  hasLeftChild(index) { return this.getLeftChildIndex(index) < this.heap.length; }
  hasRightChild(index) { return this.getRightChildIndex(index) < this.heap.length; }
  hasParent(index) { return this.getParentIndex(index) > 0 };
    
  leftChild(index) { return this.heap[this.getLeftChildIndex(index)]; }
  rightChild(index) { return this.heap[this.getRightChildIndex(index)]; }
  parent(index) { return this.heap[this.getParentIndex(index)]; }

  heapifyUp() {
    var index = this.heap.length - 1;
    while(this.hasParent(index) && this.parent(index) > this.heap[index]) {
      this.swap(this.getParentIndex(index), index);
      index = this.getParentIndex(index); 
    }
  }
    
  heapifyDown() {
    var index  = 0;
    while(this.hasLeftChild(index)) {
      var smallerChildIndex = this.getLeftChildIndex(index);
      if(this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {
        smallerChildIndex = this.getRightChildIndex(index);
      }
        
      if(this.heap[index] < this.heap[smallerChildIndex]) {
        // No need to continue, we are in order
        break;
      } 
        
      this.swap(index, smallerChildIndex);
      index = smallerChildIndex;
        
    }
  }
      
  swap(index1, index2) {
    var temp = this.heap[index1];
    this.heap[index1] = this.heap[index2];
    this.heap[index2] = temp;
  }
    
  peek() {
    if(this.heap.length === 0) throw Error("Error: Heap underflow");
    return this.heap[0];
  }
    
  getSize() {
    return this.heap.length;
  }
    
  isEmpty() {
    return this.heap.length === 0;
  }
    
  remove() {
    if(this.heap.length === 0) throw Error("Error: Heap underflow");
    var item = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown();
    return item;
  }
    
  add(item) {
    this.heap.push(item);
    this.heapifyUp();
  }
}

Test Case Fail:

var heap = new MinHeap();
var list = [];
heap.add(1);
heap.add(1);
heap.add(2);
list.push(heap.remove());
heap.add(4);
list.push(heap.remove());
heap.add(3);
list.push(heap.remove());
heap.add(6);
list.push(heap.remove());
heap.add(3);
list.push(heap.remove());
heap.add(4);
list.push(heap.remove());
heap.add(5);
list.push(heap.remove());
list.push(heap.remove());
list.push(heap.remove());
console.log(list); // logs [1,1,2,3,4,3,4,5,6]

Something is wrong with my logic but can't seem to figure it out.

heap javascript
2 Answers

The problem is in the line

hasParent(index) { return this.getParentIndex(index) > 0 };

which should be

hasParent(index) { return this.getParentIndex(index) >= 0 };

or

hasParent(index) { return index > 0 };

With the broken implementation, adding 3 to the heap [4, 6] does not propagate it up properly, because index 2 is not considered to have a parent.

user_10485720

Bergi pointed our that, in this particular implementation, hasParent() could be simplified to an expression that's so minimal it's probably better to inline it.

For developers arriving at this question looking for a good way to program a min heap in JavaScript, I've worked on making an implementation that's as clear as possible:

class MinHeap {
  constructor() {
    this.data = [];
  }

  peak() {
    return this.data[0];
  }

  push(value) {
    this.data.push(value);

    let i = this.data.length - 1;
    while (i > 0) {
      const parentIndex = Math.ceil((i / 2) - 1);
      if (this.data[i] < this.data[parentIndex]) {
        this.swap(i, parentIndex);
        i = parentIndex;
      } else {
        break;
      }
    }
  }

  pop() {
    // 1 or no remaining items is a special case
    if (this.data.length < 2) {
      return this.data.pop();
    }

    const min = this.data[0];
    this.data[0] = this.data.pop();

    let i = 0;
    while (true) {
      const [leftIndex, rightIndex] = [(i * 2) + 1, (i * 2) + 2];
      const leftValue = this.data[leftIndex] ?? Infinity;
      const rightValue = this.data[rightIndex] ?? Infinity;

      // If both children are larger than the candidate, we're done.
      if (leftValue > this.data[i] && rightValue > this.data[i]) {
        break;
      }

      // Otherwise pick the index of the smallest value
      const smallestIndex = leftValue < rightValue ? leftIndex : rightIndex;

      this.swap(i, smallestIndex);
      i = smallestIndex;
    }

    return min;
  };

  swap(i1, i2) {
    const val1 = this.data[i1];
    this.data[i1] = this.data[i2];
    this.data[i2] = val1;
  }
}

Usage and behavior:

const heap = new MinHeap();
heap.push(2);
heap.push(1);
heap.push(3);

heap.pop(); // 1
heap.pop(); // 2
heap.pop(); // 3

Suggestions for improvements is welcome! There is also a full explanation of the approach for people that aren't familiar with the array-backed-tree and "sink" and "float" heap algorithms.

user_4922540
Related