huffman tree

ht.js

var Node = function(value, left, right, word){
  this.value = value;
  this.left  = left;
  this.right = right;
  this.word  = word;
};
var HuffmanTree = function(wordcount){
  this.list = [];
  for (var word in wordcount) {
    this.list.push(new Node(wordcount[word], null, null, word));
  }
  this.list.sort(function(a, b){ return a.value > b.value; });
};
HuffmanTree.prototype.extractMin = function(){
  return this.list.shift();
};
HuffmanTree.prototype.insert = function(node){
  for (var i=0;i<this.list.length;i++) {
    if(node.value <= this.list[i].value) {
      var tmp = this.list.slice(0, i);
      this.list = tmp.concat([node], this.list.slice(i));
      return;
    }
  }
  this.list.push(node);
};
HuffmanTree.prototype.build = function(){
  while(this.list.length > 1) {
    var left  = this.extractMin();
    var right = this.extractMin();
    var value = left.value + right.value;
    this.insert(new Node(value, left, right, null));
  }
  return this.list[0];
};

// test
var str = "aabbccccddddeeeeeeeeffff";
var wordcount = {};
for (var i=0;i<str.length;i++) {
  if (str[i] in wordcount) {
    wordcount[str[i]] += 1;
  } else {
    wordcount[str[i]] = 1;
  }
}
var ht = new HuffmanTree(wordcount);
console.log(ht.build());