Heaps of Trees!

I love subjects that can be both simple and extremely complex and trees fit perfectly into that description.

Basic trees

The idea of a tree is fairly simple: a collection of connected nodes without cycles.

A tree:

Not a tree (notice the cycle):

The best layman example of a tree would be a family tree. Each node is a person and they are connected to each other based on their parent-child relationship.

The most common form of tree is a binary tree (see tree diagram above). More reading on basic trees can be found here:
Data Structures & Algos: Binary Trees
Trees (in Python)

Intro to heaps!

A heap is a kind of binary tree but with two specific properties:

  1. it is a full binary tree (meaning that every row is full except for the last one). You can't move on to a new row until all

This is not a heap because that 2 is all lonely:

  1. any node has less value than what is above it

What are heaps used for?

Heaps are best for priority queues, where you have lots of items or events but need to keep track of the ones with the highest priority. A heap will allow you to keep the most important item on top and once it's removed, the replacement will be the most important.

For such an example, you could keep all items in an unsorted list where insertion and removal are both linear time (dependent on how large the collection is), but heaps allow you to do it in log time (or better!).

You can also use heaps for sorting (though that's not much of a stretch from the data structure itself).

A Heap of Code!

Work in progress | I still need to finish writing tests for this using Jasmine and that will hopefully be uploaded to a repo in GitHub. There may be edge cases I'm not accounting for.

var binaryHeap = function(data) {
  this.storage  = [];

  if(data && (data instanceof Array)) {
    this.storage = data;
    var length = this.storage.length;
    var mid = Math.floor((length - 1)/2); 
    for(var i = mid; i >= 0; i--) {
      this.bubbleDown(i, this.storage[i]);
    }
  }
};

binaryHeap.prototype.add = function(data) {
  this.storage.push(data);
  this.bubbleUp(this.storage.length - 1, data);
};

binaryHeap.prototype.getParent = function(childIndex) {
  return Math.floor((childIndex - 1)/2);
};
binaryHeap.prototype.getLeft = function(parentIndex) {
  return parentIndex*2 + 1;
};
binaryHeap.prototype.getRight = function(parentIndex){
  return parentIndex*2 + 2;
};

binaryHeap.prototype.bubbleUp = function(childIndex, childData) {
  if(childIndex > 0) {
    var parentData = this.storage[parentIndex];
    var parentIndex = this.getParent(childIndex);

    if(this.shouldSwap(childData, parentData)) {
      this.storage[parentIndex] = childData;
      this.storage[childIndex] = parentData;
      this.bubbleUp(parentIndex, childData);
    }
  }
};

binaryHeap.prototype.bubbleDown = function(parentIndex, parentData) {
  if(parentIndex < this.storage.length) {
    var leftChildIndex = this.getLeft(parentIndex);
    var rightChildIndex = this.getRight(parentIndex);
    var targetIndex = parentIndex;
    var targetData = parentData;

    var swap = function(index, array, shouldSwap) {
      if(index < storage.length) {
        var data = storage[index];

        if(shouldSwap(data, targetData)) {
          targetIndex = index;
          targetData = data;
        }
      }
    };
    swap(rightChildIndex, this.storage, this.shouldSwap);
    swap(leftChildIndex, this.storage, this.shouldSwap);

    if(targetIndex !== parentIndex) {
      this.storage[parentIndex] = targetData;
      this.storage[targetIndex] = parentData;
      this.bubbleDown(targetIndex, parentData);
    }
  }
};

binaryHeap.prototype.removeHead = function() {
  var head = this.storage[0];
  var tail = this.storage.pop();
  this.storage[0] = tail;
  this.bubbleDown(0, tail);

  return head;
};