Min Heap Implementation

Question

Min Heap Implementation

As an exercise, I wanted to implement a min heap using JavaScript.

I'm not terribly familiar with JavaScript best practices, so I wanted to get feedback on my approach.

Notes

• I decided to implement the min heap using an array.
  • I filled the first element with a null value to make some of the math a little easier (in my opinion) - I know this is slightly more memory, but I thought the tradeoff was worth it
• The actual MinHeap function is effectively a factory function (and not a constructor) that creates objects representing min heaps that wraps the underlying array implementation in closure.
  • The idea here was to minimize the public API (i.e. "privatize" as much of the internal implementation details as possible).
  • I explicitly named functions so that if any errors occurred, it would be easier to identify in the stack trace - I don't know if this preferred / matters
• In the future, I could see this heap implementation expanding past a min heap to take a custom comparator, but I decided to keep it simple for the time being and simply use <.
• I decided to write this in ES5 - I'll probably refactor this to use ES6 conventions in the future.

Questions

The questions I have are

1. Is the factory function approach sound?
2. Are there any JavaScript best practices that I've violated or ignored?
3. Is my implementation flawed in any way?

Implementation

var MinHeap = function() {
  var values = [null];

  function getParentIndex(childIndex) {
    return Math.floor(childIndex / 2);
  }

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

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

  function swap(firstIndex, secondIndex) {
    var firstValue = values[firstIndex];

    values[firstIndex] = values[secondIndex];
    values[secondIndex] = firstValue;
  }

  function getSmallestNode(firstIndex, secondIndex) {
    var firstValue = values[firstIndex];
    var secondValue = values[secondIndex];

    if (firstValue > secondValue) {
      return {
        value: secondValue,
        index: secondIndex,
      };
    }

    return {
      value: firstValue,
      index: firstIndex,
    };
  }

  function add(value) {
    var valueIndex,
        parentIndex,
        parentValue;

    values.push(value);

    valueIndex = getSize();
    parentIndex = getParentIndex(valueIndex);
    parentValue = values[parentIndex];

    while (parentValue > value && parentIndex >= 1) {
      swap(parentIndex, valueIndex);

      valueIndex = parentIndex;
      parentIndex = getParentIndex(valueIndex);
      parentValue = values[parentIndex];
    }
  }

  function remove() {
    var firstValue = values[1],
        lastValueIndex = values.length - 1,
        lastValue = values.splice(lastValueIndex, 1)[0];

    if (getSize() > 0) {
      values[1] = lastValue;
      lastValueIndex = 1;

      var childIndices = getChildIndices(lastValueIndex);
      var smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);

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

        var childIndices = getChildIndices(lastValueIndex);
        smallestNode = getSmallestNode(childIndices.leftChild, childIndices.rightChild);
      }
    }

    return firstValue;
  }

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

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

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

Answer 1

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;
}