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() > 0) {
// becomes
if (API.size > 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 => idx >> 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" > "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 > 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 > 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 = () => {
const heap = [undefined];
const childIdxs = (idx, res = {}) => (res.right = (res.left = idx << 1) + 1, res);
const swap = (idxA, idxB) => {
const temp = heap[idxA];
heap[idxA] = heap[idxB];
heap[idxB] = temp;
}
const smallestNode = (idxs, res = {}) => {
res.idx = heap[idxs.left] > 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 >> 1;
parentVal = heap[parentIdx];
while (parentVal > val && parentIdx >= 1) {
swap(parentIdx, idx);
parentIdx = (idx = parentIdx) >> 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 > 0) {
let lastIdx = 1;
const indices = childIdxs(lastIdx);
const smallest = smallestNode(indices);
heap[1] = lastVal;
while (lastVal > 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;
}
.add()
expected to handle only integer input? \$\endgroup\$.add()
,.getFirst()
returns a different result. Consider the test case input[ "5", "14", "23", "32", "41", "87", "90", "50", "64", "53" ]
for which each element is passed to.add()
..getFirst() // "14"
. Where input to.add()
are the values as integers.getFirst() // 5
. Only noting that the expected type of input (string, integer, or either) could be specified explicitly in comments at the code, or the code could be adjusted to handle string or integer input without explicitly stating that in comments. \$\endgroup\$