Binary Heap

Welcome coders, gamers, and other awesome people who are taking the time out to read this. So recently I dove into yet another intriguing toy problem, her name Binary Heap, and man was it a hell of a challenge. First I will do a bit of explaining on what exactly binary heap is.

A heap is a special kind of tree in which a parent node is ordered only in respect to its immediate children. Unlike the binary search tree you may have implemented, where the entire tree is ordered, in a heap, the only order guaranteed is between a node and its parent.

In a binary heap, each node should have only zero, one, or two children. Each node must have 2 children before the next oldest node can have any children. Therefore the 0th node will be the parent of the 1st and 2nd nodes, the 1st node will be the parent of the 3rd and 4th nodes, and the 2nd node will be the parent of the 5th and 6th nodes. In a specific kind of binary heap, the binary min-heap, every node is less than its immediate children.

So now that we have a clear description of what exactly binary heap is let us take a look at my implementation of how I think the problem can be solved.

function BinaryHeap() {
  this._heap = [];
  this._compare = function(i, j) { return i < j; };
  this._minChild = function(i, j) { 
    return this._heap[i] < this._heap[j] ? i : j;
  };
  this._swap = function(i, j) { 
    var temp = this._heap[j];
    this._heap[j] = this._heap[i];
    this._heap[i] = temp;
  };
}
BinaryHeap.prototype.getRoot = function() {
  return this._heap[0];
};

So next I Had to add some more functionality to the code to make it actually be able to classify as a binary heap.

Implement the insert and remove root methods, each operating in logarithmic time relative to the size of the heap and each restoring the heap's property of parent to child sorting. Use the equations above to navigate parent/child relationships in the storage array, and write any helper functions needed to assist you.

Insert methods

BinaryHeap.prototype.insert = function(value) {
  let j = this._heap.length, i;
  this._heap.push(value);
  while (j !== 0) {
    i = j;
    j = Math.floor( (i - 1) / 2 );
    if (this._compare(this._heap[i], this._heap[j])) {
      this._swap(i, j);
    }
  }
};

Remove Root method

BinaryHeap.prototype.removeRoot = function() {
  this._swap(0, this._heap.length - 1);
  const removed = this._heap.pop();
  let i = 0, j;
  while (i < this._heap.length) {
    j = i;
    i = this._minChild(j * 2 + 1, j * 2 + 2);
    if (this._compare(this._heap[i], this._heap[j])) {
      this._swap(i, j);
    }
  }
  return removed;
};

Honestly thinking back on this problem it actually was not that bad of a toy problem. A lot of the work I do for these problems has just become a mini-brain warm-up I do in the morning, which can be really helpful. So yeah that's the end pretty crazy right, but I'm super interested to dive into more toy problems in the future. Stay safe during this rough time in the world and remember to keep washing your hands and to keep practicing social distancing. I'm out thanks for reading see you cool beans in the next one.