Skip to content

MinHeap implementation in JavaScript

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