Find Median from a Data Stream

1-find-median-data-stream.js

// Implement a data structure that’ll store a dynamically growing list of integers and provide access to their median in O(1)
class medianOfStream {
  // elements smaller than current median (max-heap)
  heapSmall = new Heap();
  // elements larger than current median (min-heap)
  heapLarge = new Heap();

  length() {
    // total length is a sum of both heaps lengths
    return this.heapSmall.length() + this.heapLarge.length();
  }

  // since heapSmall should be max-heap, and we just want to reuse Heap class
  // some helpers to achieve that
  addSmall(num) {
    this.heapSmall.push(-num);
  }
  peekSmall() {
    return -this.heapSmall.peekTop();
  }
  deleteSmall() {
    return -this.heapSmall.deleteTop();
  }

  // This function should take a number and store it
  insertNum(num) {
    if (this.length() === 0) {
      // if its a first number just push it to the smallest heap
      this.addSmall(num);
      return;
    }

    if (num <= this.findMedian()) {
      // if num is smaller or equal to the current median,
      // push it to small heap
      this.addSmall(num);
    } else {
      // otherwise push it to large heap
      this.heapLarge.push(num);
    }

    // check heap rebalance condition -
    // if large heap length is greater than small heap length,
    // we need to rebalance (move some elements from large heap to small heap)
    const checkLarge = () => {
      return this.heapLarge.length() > this.heapSmall.length();
    };

    // check heap rebalance condition -
    // if small heap length is greater than (large heap length + 1),
    // we need to rebalance (move some elements from small heap to large heap)
    const checkSmall = () => {
      return this.heapSmall.length() > this.heapLarge.length() + 1;
    };

    // rebalance until both rebalance conditions are not met
    while (checkSmall() || checkLarge()) {
      if (checkSmall()) {
        // small heap is greater than (large heap length + 1),
        // move elements from small to large
        this.heapLarge.push(this.deleteSmall());
      } else if (checkLarge()) {
        // large heap is greater than small heap length,
        // move elements from large to small
        this.addSmall(this.heapLarge.deleteTop());
      }
    }
  }

  // This function should return the median of the stored numbers
  findMedian() {
    // if we have even number of numbers in our heap, take both tops, and make average
    if (this.length() % 2 === 0) {
      return (this.peekSmall() + this.heapLarge.peekTop()) / 2;
    }
    // otherwise smallHeap top is the median
    return this.peekSmall();
  }
}

2-README.md