不明白“整数流的中位数”为啥用max heap和min heap比binary sort 好# JobHunting - 待字闺中
c*h
1 楼
原题在这里：
http://www.geeksforgeeks.org/median-of-stream-of-integers-runni
Given that integers are read from a data stream. Find median of elements
read so for in efficient way. For simplicity assume there are no duplicates.
For example, let us consider the stream 5, 15, 1, 3 …
After reading 1st element of stream - 5 -> median - 5
After reading 2nd element of stream - 5, 15 -> median - 10
After reading 3rd element of stream - 5, 15, 1 -> median - 5
After reading 4th element of stream - 5, 15, 1, 3 -> median - 4, so on...
每新进一个数，就binary search放进sorted array，记录一个录入几个数；取中间一
个或中间两个平均就是；时间复杂度对第n的进来的数就是O（nlogn）。
用两个heap做，难道不是一样的吗？每次heapify不就是个二查的过程吗？如果你非要
说heapify 的tighter bound is O(n) and upper bound is O(n log n)；那同样情况
的binary sort的tighter bound也是O(n)啊。
高手请指教！多谢！！！
http://www.geeksforgeeks.org/median-of-stream-of-integers-runni
Given that integers are read from a data stream. Find median of elements
read so for in efficient way. For simplicity assume there are no duplicates.
For example, let us consider the stream 5, 15, 1, 3 …
After reading 1st element of stream - 5 -> median - 5
After reading 2nd element of stream - 5, 15 -> median - 10
After reading 3rd element of stream - 5, 15, 1 -> median - 5
After reading 4th element of stream - 5, 15, 1, 3 -> median - 4, so on...
每新进一个数，就binary search放进sorted array，记录一个录入几个数；取中间一
个或中间两个平均就是；时间复杂度对第n的进来的数就是O（nlogn）。
用两个heap做，难道不是一样的吗？每次heapify不就是个二查的过程吗？如果你非要
说heapify 的tighter bound is O(n) and upper bound is O(n log n)；那同样情况
的binary sort的tighter bound也是O(n)啊。
高手请指教！多谢！！！
