MinHeap implementation in JavaScript

Enrico Hochkoeppler Profile

By Enrico Hochkoeppler

Web Developer & TutoriaLibre Founder

Example:


class MinHeap {

  constructor() {

    this.heap = [];

  }



  _getParentIndex(i) {

    return Math.floor((i - 1) / 2);

  }



  _getLeftChildIndex(i) {

    return 2 * i + 1;

  }



  _getRightChildIndex(i) {

    return 2 * i + 2;

  }



  _getParent(i) {

    return this.heap[this._getParentIndex(i)];

  }



  _getLeftChild(i) {

    return this.heap[this._getLeftChildIndex(i)];

  }



  _getRightChild(i) {

    return this.heap[this._getRightChildIndex(i)];

  }



  _hasParent(i) {

    return this._getParentIndex(i) >= 0;

  }



  _hasLeftChild(i) {

    return this._getLeftChildIndex(i) < this.heap.length;

  }



  _hasRightChild(i) {

    return this._getRightChildIndex(i) < this.heap.length;

  }



  _swap(i, j) {

    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];

  }



  _heapifyUp() {

    let i = this.heap.length - 1;

    while (this._hasParent(i) && this._getParent(i) > this.heap[i]) {

      let pi = this._getParentIndex(i);

      this._swap(i, pi);

      i = pi;

    }

  }



  _heapifyDown() {

    let i = 0;

    while (this._hasLeftChild(i)) {

      let smallerIndex = this._getLeftChildIndex(i);

      if (

        this._hasRightChild(i) &&

        this._getRightChild(i) < this._getLeftChild(i)

      ) {

        smallerIndex = this._getRightChildIndex(i);

      }

      if (this.heap[i] <= this.heap[smallerIndex]) {

        break;

      }

      this._swap(i, smallerIndex);

      i = smallerIndex;

    }

  }



  push(item) {

    this.heap.push(item);

    this._heapifyUp();

  }



  isEmpty() {

    return this.heap.length === 0;

  }



  pop() {

    if (this.isEmpty()) {

      return null;

    }

    if (this.heap.length === 1) {

      return this.heap.pop();

    }

    const min = this.heap[0];

    this.heap[0] = this.heap.pop();

    this._heapifyDown();

    return min;

  }



  peek() {

    return this.heap[0];

  }

}

Found this helpful? Share the knowledge...

... or support this project to keep it alive!

Buy Me a Coffee

Previous

Promises

Next

DOM & Events