util_data_heap.js

/**
 * @module Heap
 * @fileoverview Contains Heap class.
 */

/**
 * @class
 * Heap data structure. Can be used as a min or max heap with
 * a custom comparison function.
 */
class Heap {
    /**
     * Create a new Heap.
     * @param {any[]} items Items to add
     * @param {function} func Function for comparing two items
     * @constructor
     */
    constructor(items = [], func = (a, b) => { return a < b; }) {
        this.data = [];

        this.func = func;

        this.size = 0;

        for (const item of items)
            this.add(item);
    }

    /**
     * Get the index of the parent of a specified node.
     * @param {number} i Index of node to get parent of
     * @returns {number} Index of parent node
     * @private
     */
    _p(i) {
        return Math.floor((i - 1) / 2);
    }

    /**
     * Get the index of the left child of a specified node.
     * @param {number} i Index of node to get left child of
     * @returns {number} Index of left child node
     * @private
     */
    _l(i) {
        return (2 * i) + 1;
    }

    /**
     * Get the index of the right child of a specified node.
     * @param {number} i Index of node to get right child of
     * @returns {number} Index of right child node
     * @private
     */
    _r(i) {
        return (2 * i) + 2;
    }

    /**
     * Heapify the Heap in the upward direction (percolate up).
     * @param {number} i Index to start at
     * @private
     */
    _heapifyUp(i) {
        if (i === 0)
            return;

        if (this.data.length <= 1)
            return;

        const p = this._p(i);

        const a = this.data[i];
        const b = this.data[p];

        if (this.func(a, b)) {
            const temp = a;

            this.data[i] = b;
            this.data[p] = temp;

            this._heapifyUp(p);
        }
    }

    /**
     * Heapify the Heap in the downward direction (percolate down).
     * @param {number} i Index to start at
     * @private
     */
    _heapifyDown(i) {
        if (i === this.data.length - 1)
            return;

        if (this.data.length <= 1)
            return;

        let min = i;

        const l = this._l(i);
        const r = this._r(i);

        const a = this.data[i];
        const b = this.data[l];
        const c = this.data[r];

        if (l < this.data.length && !this.func(a, b))
            min = l;

        if (r < this.data.length && !this.func(a, c))
            min = r;

        if (min !== i) {
            this.data[i] = this.data[min];
            this.data[min] = a;
            this._heapifyDown(min);
        }
    }

    /**
     * Add an item to the heap. Will append the item to the end of the array and heapify after.
     * @param {any} item Item to add
     */
    add(item) {
        const i = this.data.length;
        this.data.push(item);

        this.size++;

        this._heapifyUp(i);
    }

    /**
     * Peek at the root value of the Heap.
     * @returns {any} Root value of the Heap
     */
    peek() {
        return this.data[0];
    }

    /**
     * Pop the root of the Heap. Will swap the last item with the root, remove the original, and heapify after.
     * @returns {any} Root value of the Heap
     */
    pop() {
        const val = this.data[0];

        const end = this.size - 1;

        this.data[0] = this.data[end];
        this.data.splice(end, 1);

        this.size--;

        this._heapifyDown(0);

        return val;
    }

    /**
     * Check if a value exists in the Heap, using a specific function. Because of the custom function, the search must
     * be done by iterating over every single value in the raw array.
     * @param {function} func Function to check with
     * @returns {boolean} Whether or not the Heap contains a value fulfilling the requirements of the custom function
     */
    hasCustom(func = (v) => { return false; }) {
        for (const val of this.data) {
            if (func !== null)
                if (func(val))
                    return true;
        }

        return false;
    }
}

export default Heap;