x 295. Find Median from Data Stream

time: O(nlogn): heapify: nlogn, insert && remove: logn

space: O(n)

var MedianFinder = function () {
    this.small = new Heap([], (a, b) => a - b > 0);
    this.large = new Heap([], (a, b) => a - b < 0);
    this.even = true;
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function (num) {
    if (this.even) {
        this.large.insert(num);
        const largeFromSmall = this.large.remove();
        this.small.insert(largeFromSmall);
    } else {
        this.small.insert(num)
        const largeFromSmall = this.small.remove();
        this.large.insert(largeFromSmall);
    }

    this.even = !this.even;
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function () {
    if (this.even) {
        return (this.small.heap[0] + this.large.heap[0]) / 2;
    } else {
        return this.small.heap[0];
    }
};

/** 
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */

class Heap {
    constructor(arr, predicate = (a, b) => a < b) {
        this.predicate = predicate;
        this.heap = this.buildHeap(arr);
    }

    buildHeap(arr) {
        let currentIndex = Math.floor((arr.length - 1 - 1) / 2);
        while (currentIndex >= 0) {
            this.siftDown(arr, currentIndex, arr.length - 1);
            currentIndex--;
        }

        return arr;
    }

    siftDown(heap, currentIndex, endIndex) {
        let left = currentIndex * 2 + 1;

        while (left <= endIndex) {
            let min = left;
            let right = currentIndex * 2 + 2;
            if (heap[right] !== undefined && this.predicate(heap[right], heap[min])) {
                min = right;
            }

            if (this.predicate(heap[currentIndex], heap[min])) break;
            this.swap(heap, currentIndex, min);
            currentIndex = min;
            left = currentIndex * 2 + 1;
        }
    }

    siftUp(heap, currentIndex) {
        let parentIndex = Math.floor((currentIndex - 1) / 2);
        while (parentIndex >= 0) {
            if (this.predicate(heap[parentIndex], heap[currentIndex])) {
                break;
            }

            this.swap(heap, parentIndex, currentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor((currentIndex - 1) / 2);
        }

        return heap;
    }

    insert(v) {
        this.heap.push(v);
        this.size++;

        this.siftUp(this.heap, this.heap.length - 1);
    }

    remove() {
        this.swap(this.heap, 0, this.heap.length - 1);
        const elementToRemove = this.heap.pop();
        this.size--;
        
        this.siftDown(this.heap, 0, this.heap.length - 1);
        return elementToRemove;
    }

    swap(arr, a, b) {
        const temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
        return arr;
    }
}

Last updated