[JS] Median stream

medianStream.js

function getParent(i) {
  return  Math.floor(i + 1 / 2) - 1;
} 
   
function addHeap(heap, val, comparator) {
  heap.push(val);
  let currentIdx = heap.length - 1;
  let parentIdx = getParent(currentIdx);

  while(currentIdx > 0 && comparator(heap[currentIdx], heap[parentIdx])) {
    swap(heap, currentIdx, parentIdx);
    currentIdx = parentIdx;
    parentIdx = getParent(currentIdx);
  }
} 

function addMinHeap(heap, val) {
  return addHeap(heap, val, (a, b) => a < b);
} 

function addMaxHeap(heap, val) {
  return addHeap(heap, val, (a, b) => a > b);
} 

function swap(heap, i, j) {
  const aux = heap[i];
  heap[i] = heap[j];
  heap[j] = aux;  
}

function getMedian(a, b) {
  return Math.floor((a + b) / 2);
}

function rebalance(minHeap, maxHeap) {
  let smallerHeap;
  let biggerHeap;
  let addHeap;
  let descendHeap;
  if(minHeap.length > maxHeap.length) {
    smallerHeap = maxHeap;
    biggerHeap = minHeap;
    addHeap = addMaxHeap;
    descendHeap = descendMinHeap;
  }
  else {
    smallerHeap = minHeap;
    biggerHeap = maxHeap;
    addHeap = addMinHeap;
    descendHeap = descendMaxHeap;
  }
  
  const newValue = biggerHeap[0];
  biggerHeap[0] = biggerHeap[biggerHeap.length - 1];
  biggerHeap.splice(biggerHeap.length - 1, 1);
  descendHeap(biggerHeap);
  addHeap(smallerHeap, newValue);  
}

function descendHeap(heap, comparator) {
  const len = heap.length;
  const half = Math.floor(len / 2) - 1;
  let pos = 0;
  while(pos <= half) {
    const leftIdx = 2 * pos + 1;
    const rightIdx = 2 * pos + 2;
    let targetIdx = pos;
    if(leftIdx < len && comparator(heap[leftIdx], heap[targetIdx])) targetIdx = leftIdx;
    if(rightIdx < len && comparator(heap[rightIdx], heap[targetIdx])) targetIdx = rightIdx;
    if(targetIdx != pos) {
      swap(heap, pos, targetIdx);
      pos = targetIdx;
    }
    else break;
  }
}

function descendMaxHeap(heap) {
  return descendHeap(heap, (a, b) => a >  b);
}

function descendMinHeap(heap) {
  return descendHeap(heap, (a, b) => a <  b);
}

function findMedian(arr) {
  const minHeap = [];
  const maxHeap = [];
  const result = [];
  
  arr.forEach(num => {
    if(!minHeap.length || num >= minHeap[0]) addMinHeap(minHeap, num);
    else addMaxHeap(maxHeap, num);
    
    let diff = minHeap.length - maxHeap.length; 
    if(Math.abs(diff) > 1) {
      rebalance(minHeap, maxHeap);
    }

    diff = minHeap.length - maxHeap.length; 
    if(diff === 1)  result.push(minHeap[0]);
    else if(diff === -1)  result.push(maxHeap[0]);  
    else {
      result.push(getMedian(minHeap[0], maxHeap[0]));      
    }
  });
  return result;
}