javascript – js implementation of a binary heap with logn key updates


I’m looking to get more into programming. I have quite a strong mathematical background but as a programmer I am quite the novice.

I was thinking it would be nice to implement a number of data structures and algorithms (in particular graph algorithms) as this has a nice mathematical flavour to it.

To start with I’ve just done a binary heap, but one where we maintain an internal map so we can quickly find elements so as to reasonably efficienctly delete and update them.

The code in full is here

https://github.com/Thrillpool/binary-heaps and index.js contains all the logic.

I am happy for any comments, but let me note that while of course a binary heap should be a performant thing as that is it’s main application, I have only intended to achieve the right big O complexity other than this the code is supposed to be as readable as possible.

Here it is in its entirety

/** @template T */
class MutableArrayBinaryHeap {
    /**
     * @param {(a: T, b: T) => number} cmp
     */
    constructor(cmp) {
        /**
         * @private
         * @type {T()}
         */
        this.internalArr = ();
        /**
         * @private
         * @type {Map<T, (number, number)>}
         */
        this.inverseMap = new Map();
        /**
         * @private
         */
        this.cmp = cmp;
    }

    /**
     * Iterates over the heap.
     *
     * @return {Iterator<T>}
     */

    *(Symbol.iterator)() {
        while (this.internalArr.length !== 0) {
            yield this.extract();
        }
    }

    /**
     * Returns true if the heap is empty
     */
    isEmpty() {
        return this.internalArr.length === 0;
    }

    /**
     * Accounts for a change to the results of cmp which means
     * el has a smaller value in the total order than it used to
     * @param {T} el
     */
    decreaseKey(el) {
        const ind = this.inverseMap.get(el)(0);
        _heapifyDown(this, ind);
    }

    /**
     * Accounts for a change to the results of cmp which means
     * el has a larger value in the total order than it used to
     * @param {T} el
     */
    increaseKey(el) {
        const ind = this.inverseMap.get(el)(0);
        _heapifyUp(this, ind);
    }

    /**
     * Inserts the given element into the binary heap
     *
     * @template {T} S S extends T
     * @param {S} el The element to insert
     */
    insert(el) {
        const candidate = this.internalArr.length;
        this.internalArr(candidate) = el;
        _setInverseMap(this, el, candidate);
        _heapifyUp(this, candidate);
    }

    /**
     * Removes one instance of the given element from the binary heap,
     * given that it exists, otherwise it does nothing
     *
     * @param {T} el the element to delete
     */
    delete(el) {
        const (indToDelete, count) = this.inverseMap.get(el);
        if (indToDelete === -1) {
            return;
        }
        if (count !== 1) {
            _popInverseMap(this, el);
            return;
        }
        _swapVertices(this, indToDelete, this.internalArr.length - 1);
        _popInverseMap(this, el);
        const cmpResult = this.cmp(this.internalArr(indToDelete), el);
        this.internalArr.length = this.internalArr.length - 1;
        if (cmpResult >= 0) {
            _heapifyUp(this, indToDelete);
        } else {
            _heapifyDown(this, indToDelete);
        }
    }

    /**
     * Construct a priority queue using the designated comparing function
     * and initialised with the elements from an iterable
     * @template S
     * @param {Iterable<S>} it
     * @param {(a: S, b: S) => number} cmp
     */
    static from(it, cmp) {
        const b = new MutableArrayBinaryHeap(cmp);
        for (const el of it) {
            const count = _setInverseMap(b, el, b.internalArr.length);
            if (count === 1) {
                b.internalArr.push(el);
            }
        }
        const levels = Math.floor(Math.log2(b.internalArr.length));
        for (let level = levels - 1; level >= 0; level--) {
            const start = Math.pow(2, level) - 1;
            for (let i = start; i < 2 * (start + 1); i++) {
                _heapifyDown(b, i);
            }
        }
        return b;
    }

    /**
     * Given the heap is non empty
     * retrieves the largest element in the heap and removes it
     */
    extract() {
        const topEl = this.peek();
        this.delete(topEl);
        return topEl;
    }

    /**
     * Given the heap is non empty returns the largest element
     */
    peek() {
        return this.internalArr(0);
    }
}

/**
 * Performs the heapify up operation on the given index, i.e. makes the
 * heap such that the elements above the element at that index in
 * the tree order are indeed larger
 * @param {MutableArrayBinaryHeap} m
 * @param {number} candidate the position of the element to heapify up
 * @returns {void} void
 */

function _heapifyUp(m, candidate) {
    const el = m.internalArr(candidate);
    while (candidate !== 0) {
        const parentIndex = Math.floor((candidate - 1) / 2);
        const parent = m.internalArr(parentIndex);
        const cmpResult = m.cmp(el, parent);
        if (cmpResult < 0) {
            m.internalArr(candidate) = el;
            break;
        }
        _swapVertices(m, candidate, parentIndex);
        candidate = parentIndex;
    }
}

/**
 * Performs the heapify down operation on the given index, i.e. makes the
 * heap such that such that the elements below the element at that index in
 * the tree order are indeed larger
 * @param {MutableArrayBinaryHeap} m
 * @param {number} ind the position of the element to heapify down
 * @returns {void} void
 */
function _heapifyDown(m, ind) {
    while (true) {
        const largestAmongstChildren = _largestAmongstChildren(m, ind);
        if (largestAmongstChildren === ind) {
            break;
        }
        _swapVertices(m, ind, largestAmongstChildren);
        ind = largestAmongstChildren;
    }
}

function _swapVertices(m, candidate, parentIndex) {
    const parent = m.internalArr(parentIndex);
    const el = m.internalArr(candidate);

    m.internalArr(candidate) = parent;
    m.internalArr(parentIndex) = el;

    const parentPair = m.inverseMap.get(parent);
    const elPair = m.inverseMap.get(el);

    parentPair(0) = candidate;
    elPair(0) = parentIndex;
}

function _setInverseMap(m, el, index) {
    if (!m.inverseMap.has(el)) {
        m.inverseMap.set(el, (index, 0));
    }
    const indexAndCount = m.inverseMap.get(el);
    indexAndCount(1) = indexAndCount(1) + 1;
    return indexAndCount(1);
}

function _popInverseMap(m, el) {
    const known = m.inverseMap.get(el);
    if (!known) {
        return (-1);
    }
    const (ind, count) = known;
    if (count === 1) {
        m.inverseMap.delete(el);
    } else {
        known(1) = known(1) - 1;
    }
    return (ind, count - 1);
}

function _children(m, index) {
    const length = m.internalArr.length;
    const (left, right) = (index * 2 + 1, index * 2 + 2);

    if (right < length) {
        return (left, right);
    }
    if (left >= length) {
        return ();
    }
    return (left);
}

function _largestAmongstChildren(m, index) {
    const children = _children(m, index);
    if (children.length === 0) {
        return index;
    }
    const el = m.internalArr(index);
    const largeChild = _largestChild(m, children);
    return m.cmp(el, m.internalArr(largeChild)) >= 1 ? index : largeChild;
}

function _largestChild(m, children) {
    if (children.length === 1) {
        return children(0);
    }
    const (left, right) = children;
    return m.cmp(m.internalArr(left), m.internalArr(right)) >= 1 ? left : right;
}