力扣链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
思路一：两个堆
要获取中位数我们只需要知道两个数据：较大的一半数字中最小的一个，和较小的一半数字中最大的一个。
由于只需要获取最值，考虑建立两个堆 greaterHeap 和 smallerHeap：
greaterHeap是一个最小堆，存储数组中较大的一半数字，则堆顶为较大的一半数字中最小的一个
smallerHeao是一个最大堆，存储数组中较小的一半数字，则堆顶为较小的一半数字中最大的一个
插入数字时需要调整两个堆的大小，以保持两个堆各有一半的数字，则：
当数据总数为偶数时，中位数为两个堆顶的平均数
当数据总数为奇数时，中位数为greaterHeap的堆顶（假设greaterHeap的大小始终大于等于smallerHeap）
插入数字num时：
若数据总数为奇数，则greaterHeap比smallerHeap多一个数。若num > smallerHeap.top()，先将num插入greaterHeap，再将greaterHeap的堆顶插入smallerHeap；否则直接插入smallerHeap。
若数据总数为偶数，则greaterHeap与smallerHeap个数一样，插入后应该使greaterHeap元素多一个。若num < smallerHeap.top()，先将num插入smallerHeap，再将smallerHeap的堆顶插入greaterHeap；否则直接插入greaterHeap。
代码：
/** * initialize your data structure here. */ var MedianFinder = function() { this.greaterHeap = new Heap((x, y) => x < y); this.smallerHeap = new Heap(); }; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { const greaterLen = this.greaterHeap.size(); const smallerLen = this.smallerHeap.size(); //若两个堆大小相等，即共有偶数个数字 if(greaterLen === smallerLen){ //两个堆都为空，直接插入大堆 if(!greaterLen){ this.greaterHeap.insert(num); return; } if(num < this.smallerHeap.top()){ this.smallerHeap.insert(num); const smallerTop = this.smallerHeap.extract(); this.greaterHeap.insert(smallerTop); }else{ this.greaterHeap.insert(num); } } //两个堆大小不等，即共奇数个 else{ if(num > this.greaterHeap.top()){ this.greaterHeap.insert(num); const greaterTop = this.greaterHeap.extract(); this.smallerHeap.insert(greaterTop); }else{ this.smallerHeap.insert(num); } } }; /** * @return {number} */ MedianFinder.prototype.findMedian = function() { const greaterLen = this.greaterHeap.size(); const smallerLen = this.smallerHeap.size(); if(!greaterLen){ return null; } if(greaterLen === smallerLen){ return (this.greaterHeap.top() + this.smallerHeap.top())/2; }else{ return this.greaterHeap.top(); } }; const defaultCmp = (x, y) => x > y; // 默认是最大堆 class Heap{ constructor(cmp = defaultCmp) { this.heap = []; this.cmp = cmp; } insert(num){ this.heap.push(num); //自底向上检查是否仍然满足堆的条件 let index = this.heap.length-1; while(index){ let parent = Math.ceil(index/2)-1; if(parent >= 0 && !this.cmp(this.heap[parent], this.heap[index])){ const tmp = this.heap[index]; this.heap[index] = this.heap[parent]; this.heap[parent] = tmp; } index = parent; } } extract(){ const top = this.heap[0]; this.heap[0] = this.heap.pop(); this.heapify(0); return top; } heapify(index){ const left = 2 * index + 1; const right = 2 * index + 2; let parent = index; if(left<this.heap.length && this.cmp(this.heap[left],this.heap[parent])){ parent = left; } if(right<this.heap.length && this.cmp(this.heap[right],this.heap[parent])){ parent = right; } if(parent !== index){ //交换并继续heapify const tmp = this.heap[parent]; this.heap[parent] = this.heap[index]; this.heap[index] = tmp; this.heapify(parent); } } top(){ return this.heap[0]; } size(){ return this.heap.length; } } /** * Your MedianFinder object will be instantiated and called as such: * var obj = new MedianFinder() * obj.addNum(num) * var param_2 = obj.findMedian() */
时间复杂度：
插入：O(logN)
取中位数：O(1)
空间复杂度：O(N)
易错：
写堆的heapify算法时：
if(left<this.heap.length && this.heap[left] > this.heap[parent]){ parent = left; } if(right<this.heap.length && this.heap[right] > this.heap[parent]){ parent = right; }
if判断条件是this.heap[parent] 而不是this.heap[index]
思路二： 二分查找
最基本的找中位数的办法是排序后取最中间的数，因此只要保证每次插入后数组仍是有序的，就可以直接取最中间的数作为中位数。数组插入时，采用二分查找的方式查找插入的位置。
代码：
/** * initialize your data structure here. */ var MedianFinder = function() { this.arr = []; }; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { if(!this.arr.length){ this.arr.push(num); return; } let start = 0, end = this.arr.length - 1; //start和end相邻时退出 while(start < end - 1){ const mid = parseInt((start + end) / 2); if(this.arr[mid] === num){ //mid值和num相等，插在mid之前或之后 this.arr.splice(mid, 0, num); return; }else if(this.arr[mid] < num){ start = mid; }else{ end = mid; } } //剩下最后两个数，判断应该插在哪里 if(this.arr[start] > num){ this.arr.splice(start, 0, num); }else if(this.arr[end] < num){ this.arr.splice(end+1, 0, num); }else{ this.arr.splice(start+1, 0, num); } }; /** * @return {number} */ MedianFinder.prototype.findMedian = function() { const len = this.arr.length; if(len === 0) return null; if(len % 2 === 0){ return (this.arr[len/2] + this.arr[len/2 - 1]) / 2; }else{ return this.arr[Math.floor(len/2)]; } }; /** * Your MedianFinder object will be instantiated and called as such: * var obj = new MedianFinder() * obj.addNum(num) * var param_2 = obj.findMedian() */
时间复杂度：
插入：O(N) (logN二分查找，N插入)
取中位数：O(1)
空间复杂度：O(N)
易错：
原文：https://www.cnblogs.com/xintangchn/p/13223822.html