Min Heap

Theory

Insertion

1. Always insert at the bottom of the tree.
2. Heapify up

Heapify Up

Heapify up is only performed after insertion.

1. The root node of every sub-tree must be minimum, check the sub-tree of node's immediate parent.
2. If the parent is greater than node, swap parent with node.
3. Recursively check to the root.

Code

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

    insert(node, distance) {
        this.heap.push([node, distance]);
        this.heapifyUp();
    }

    removeMin() {
        this.swap(0, this.heap.length - 1);
        const min = this.heap.pop();
        this.heapifyDown();
        return min;
    }

    heapifyUp() {
        let index = this.heap.length - 1;
        while (
            this.hasParent(index) &&
            this.parent(index)[1] > this.heap[index][1]
        ) {
            this.swap(this.parentIndex(index), index);
            index = this.parentIndex(index);
        }
    }

    heapifyDown() {
        let index = 0;
        while (this.hasLeftChild(index)) {
            let smallerChildIndex = this.leftChildIndex(index);
            if (
                this.hasRightChild(index) &&
                this.rightChild(index)[1] < this.leftChild(index)[1]
            ) {
                smallerChildIndex = this.rightChildIndex(index);
            }

            if (this.heap[index][1] < this.heap[smallerChildIndex][1]) {
                break;
            } else {
                this.swap(index, smallerChildIndex);
            }
            index = smallerChildIndex;
        }
    }

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

    isEmpty = () => this.heap.length === 0;
    parentIndex = (index) => (index - 1) >> 1;
    hasParent = (index) => this.parentIndex(index) >= 0;
    parent = (index) => this.heap[this.parentIndex(index)];

    leftChildIndex = (index) => (index << 1) + 1;
    hasLeftChild = (index) => this.leftChildIndex(index) < this.heap.length;
    leftChild = (index) => this.heap[this.leftChildIndex(index)];

    rightChildIndex = (index) => (index << 1) + 2;
    hasRightChild = (index) => this.rightChildIndex(index) < this.heap.length;
    rightChild = (index) => this.heap[this.rightChildIndex(index)];
}

module.exports = MinHeap;

References

1. https://www.digitalocean.com/community/tutorials/min-heap-binary-tree