pairingheap.js

//pairing heap
//{elem:object, subheaps:[array of heaps]}
//subheaps might should be a linked list
function PairingHeap(obj) {
  this.elem = obj;
  this.subheaps = [];
}

function min(heap) {
  return heap.elem;
}

function empty(heap) {
  return heap.elem == null;
}

function insert(heap, obj) {
  return merge(heap, new PairingHeap(obj));
}

function merge(heap1, heap2) {
  if(empty(heap1)) return heap2;
  else if(empty(heap2)) return heap1;
  else if(heap1.elem < heap2.elem) {
    heap1.subheaps.push(heap2);
    return heap1;
  } else {
    heap2.subheaps.push(heap1);
    return heap2;
  }
}

function removeMin(heap) {
  if(empty(heap)) return null;
  else {
    return mergePairs(heap.subheaps);
  }
}

function mergePairs(heaps) {
  if(heaps.length == 0) return new PairingHeap();
  else if(heaps.length == 1) return heaps[0];
  else return merge(merge(heaps.pop(),heaps.pop()),mergePairs(heaps));
}

function decreaseKey(heap, subheap, newValue) {
  var newHeap = removeMin(subheap);
  //reassign subheap values to preserve tree
  subheap.elem = newHeap.elem;
  subheap.subheaps = newHeap.subheaps;
  insert(heap, newValue);
}