Min Heap Implementation
Questions


  Is the factory function approach sound?


Yes it is by far the best for objects that will have more than one long lived instance. Not so good for many short lived instances in which case use prototyped factory to reduce instantiation overheads, but lose some flexibility when protecting state.
For single instance object use a singleton.

Freeze

For added state safety freeze the returned object so that it can not have its state mutated

return Object.freeze({add, remove, getFirst, getSize});


Internal reference

It is often the case that you need to reference the factory object from within the factory function. We can think of the factory functions closure as the object state and the returned object as the interface.

Because in JS the token this is unsafe we need to create a safe reference to the returned object that can be used from within the factory.

What that name is, is up to you, I would personally have called it interface however that is a reserved token in JS so I have taken to standardize the returned object name to API which works well and replaces the this token with the visually easier capitalized name.

Thus you can use the following (see below for details on getters)

const API = Object.freeze({
    add, remove,
    get first() { return  values[1] },
    get size() { return values.length - 1 },
});

return API;


Then from within the factory you can acess the interface as follows

// you had
if (getSize() &gt; 0) {
// becomes
if (API.size &gt; 0) {




Q2


  Are there any JavaScript best practices that I've violated or ignored?



Use const for variables that do not change.
Use object shorthand property notation. See below
Reduce GC overhead and by using preallocation and result object as optional argument. See below
Hoist var declarations to the top of the function.
Don't use line seperated declarations.  See below
Use getters and setters to simplify the interface.
Protect state and freeze the returned factory object.
null is to be avoided. undefined is better. Ignoring the DOM null is seldom used in JS and represents a defined placeholder.
Use shorter function form that is arrow functions.
The JS author's regret was to tokenize function rather than func which spurred the push and adoption of arrow functions. Use common abbreviations when possible, less to read is quicker to read and easier to comprehend. Source code is not an english literature dissertation, you don't need to double space for examiners notes.
JS has one number type (double AKA 64 bit floating point), however almost all implementations have a variety of under the hood number types. Signed 32 integer is the fastest and can be forced by using any of the bitwise operators. If working with known integer types (eg indices) use bitwise operations to ensure internal number type is int32
Don't add inferable names to variable names. You had function getParentIndex(childIndex) { return Math.floor(childIndex / 2); } is just as effective as const parentIdx = idx =&gt; idx &gt;&gt; 1; and makes one wonder why you need a function to perform a single operator?




Q3


  Is my implementation flawed in any way?


Not if the user of it is careful. 

I do know that you can implement it without the need for the first item in the heap without adding complexity.

You do need to prevent your code from creating invalid states. Such as if you add a string as a number heap.add("1") your determination as to which is greater will false eg "11" &gt; "2" evaluates to false. To prevent that from happening you need to convert added values to Number type. (see rewrite) 

Also you do not want to accept values that are not numbers. You can throw a range error or ignore such values.

You do not protect against removing more than available and thus you can mutate the state to unusable. You should first check if there is anything to remove before doing so (see rewrite)



More info on above notes

Line separated declarations

Bad

var valueIndex,
    parentIndex,
    parentValue;


Better        

var valueIndex;
var parentIndex;
var parentValue;


Best    

var valueIndex, parentIndex, parentValue;


Shorthand property notation

Shorthand notation reduces the source code size, and thus is a major player in reducing to occurance of bugs.

eg creating an object from defined variables

var foo = someVal();
var bar = someOtherVal();

// old school ES notation
var obj = {foo : foo, bar : bar};

// ES6 + shorthand property notation
var obj = {foo, bar};


When you return the factory object    

return {
    add: add,
    remove: remove,
    getFirst: getFirst,
    getSize: getSize,
};


You can return using shorthand     

return {add, remove, getFirst, getSize};


Memory smart functions.

Memory smart functions aim to reduce the overhead that GC (Garbage collection) incurs by reducing needless memory allocations. It also has an additional benefit as it reduces the allocation and creation overheads associated with new objects and or arrays.

For example the function...

function getChildIndices(parentIndex) {
    var leftChild = parentIndex * 2;

    return {
      leftChild: leftChild,
      rightChild: leftChild + 1,
    };
}


...creates and returns a new object each time it is called. You ate just interested in the 2 64bit numbers (if ints then 32bit numbers), but an object requires much more than 2 64bit values, and it need to invoke memory management, and when done with the object it is added to the GC workload.

You call it as follows

  var childIndices = getChildIndices(lastValueIndex);  // creates new object
  var smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);

  while (lastValue &gt; smallestNode.value) {
      swap(lastValueIndex, smallestNode.index);
      lastValueIndex = smallestNode.index;

      var childIndices = getChildIndices(lastValueIndex); // Creates it again each iteration
      smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);
  }


The function can be changed to be able to remove that overhead using the following pattern

function getChildIndices(parentIndex, result = {}) {  // result is the returning object. If not passed it is created
    var leftChild = parentIndex * 2;
    result.leftChild = leftChild;
    result.rightChild = leftChild + 1;
    return result;
}


Then your calling function uses it as follows    

  const childIndices = getChildIndices(lastValueIndex);  // creates new object as default parameter
  var smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);

  while (lastValue &gt; smallestNode.value) {
      swap(lastValueIndex, smallestNode.index);
      lastValueIndex = smallestNode.index;

      getChildIndices(lastValueIndex, childIndices); // reuses the object, saving time, memory and GC overhead
      smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);
  }


Read only properties using getters

You have the following functions that are equivalent to getters (hint they have get at the start of the name)

function getFirst() {
    return values[1];
}

function getSize() {
    return values.length - 1;
}

return {
    add: add,
    remove: remove,
    getFirst: getFirst,
    getSize: getSize,
};


Should be defined as getters    

return Object.freeze({
    add, remove,
    get first() { return  values[1] },
    get size() { return values.length - 1 },
});


A rewrite

I have added some additional state protection to the interface. Done some renaming, and reduced memory management overheads. The whole thing is now 50 lines that easily fits a display meaning the whole function can be understood without any device interaction

const MinHeap = () =&gt; {
    const heap = [undefined];
    const childIdxs = (idx, res = {}) =&gt; (res.right = (res.left = idx &lt;&lt; 1) + 1, res);
    const swap = (idxA, idxB) =&gt; {
        const temp = heap[idxA];
        heap[idxA] = heap[idxB];
        heap[idxB] = temp;
    }
    const smallestNode = (idxs, res = {}) =&gt; {
        res.idx = heap[idxs.left] &gt; heap[idxs.right] ? idxs.right : idxs.left;
        res.val = heap[res.idx];
        return res;
    }
    const API = Object.freeze({
        add(val) {
            if (isNaN(val)) { throw new RangeError("Can only add numeric values") }
            var idx, parentIdx, parentVal;
            heap.push(Number(val));
            idx = API.size;
            parentIdx = idx &gt;&gt; 1;
            parentVal = heap[parentIdx];
            while (parentVal &gt; val &amp;&amp; parentIdx &gt;= 1) {
                swap(parentIdx, idx);
                parentIdx = (idx = parentIdx) &gt;&gt; 1;
                parentVal = heap[parentIdx];
            }
        },
        remove() { // returns undefined if heap is empty
            if (API.size) {
                let lastVal = heap.pop();
                const first = heap[1];
                if (API.size &gt; 0) {
                    let lastIdx = 1;
                    const indices = childIdxs(lastIdx);
                    const smallest = smallestNode(indices);
                    heap[1] = lastVal;
                    while (lastVal &gt; smallest.val) {
                        swap(lastIdx, smallest.idx);
                        lastIdx = smallest.idx;
                        smallestNode(childIdxs(lastIdx, indices), smallest);
                    }
                }
                return first;
            }
        },
        get first() { return heap[1] },
        get size() { return heap.length - 1 },
    });
    return API;
}