1美大学研究生 数据结构与算法 的 第一次作业， 提问：）， 关于heap
求助， 我的第一个assignment， 前面2个题目，已经搞定。 最后1个，还没有idea， 求助。
Dynamic median.
Using the Abstrode Data Type( A bounded Queue--- using a ring buffer, 和 priorityQueue -- maximal-heap, or min-heap), implement Dynamic median that dynamically maintains the min, median, and max elements of the last N items in a data stream. N可以被4整除。
[align=center]DynamicMedian<T>[/align]
DynamicMedian<T> (int size)
Insert(T Value) Adds an element inserted N call ago is removed.
T min() Return the least element of the last N inserted.
T median() Return the median element of the last N inserted
T max() Returns the greatest element of the last N inserted
------------------------------------------
Note.
1) use a bounded queue and some priority queues
2) Insert() = logn time.
3 min(), max(), median() operations = O(1) time.
4 if min, median, max is called before N elements have been inserted, fail
5 also maintain the 25% and 75% quaritiles
请问，谁能说说大概实现原理，如何构建之类的？ 我已经做好了 bounded queue，和priority queue的数据结构。 我还没有想到如何做median的。
谢谢了。
[解决办法]
If you want to know the median value in order, e.g. the N/2 biggest value, it's easy to retrieve from INDEX as well
When the first N-length INDEX queue is created, you can go down from first element to the [N/2] to know which entry is the median
When the N-Length INDEX queue is updated
If the value is insert before the median, you can get previous value of the current Median value
if the value is insert after the median value, you can get next entry of the value
If an entry is removed, you need to update the median value in the similar way.
Thus you only need to keep a pointer to the entry in the INDEX queue for the median value.
Do you get it?
