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