数据流中位数算法设计：利用堆实现高效中位数查找

"数据结构课程设计报告 - 随时找到数据流中的中位数" 在数据结构课程设计中，报告的主题聚焦于设计一个名为MedianHolder的结构，目的是在数据流不断输入整数的情况下，能实时地计算并返回当前所有输入数的中位数。设计要求对新数的插入操作具有O(logN)的时间复杂度，同时获取中位数的时间复杂度为O(1)。 首先，我们来看传统的解决方法。最直观的方式是维护一个有序序列A。当新数到来时，我们需要通过二分查找找到它在序列中的正确位置，然后进行插入，确保序列依然有序。然而，这种方法在插入新数时的时间复杂度为O(logN)（二分查找）加上O(N)（调整序列），总时间复杂度为O(N)，不符合设计要求。另外，查询中位数的时间复杂度是O(1)。 如果序列以链式存储，虽然插入新数时寻找合适位置的时间可以降低到O(N)，但是调整元素顺序以保持有序状态仍然需要O(1)的时间。但这导致查询中位数的时间复杂度上升到O(N)，同样不满足要求。 接着，报告提到了尝试使用二分搜索树。虽然二分搜索树在插入操作上的时间复杂度为O(logN)，但由于每个节点需要维护子孙节点的个数，寻找中位数的时间复杂度提高到O(logN)，所以这个方案也不适用。 最后，报告提出了使用堆这一数据结构来解决问题。堆是一种特殊的树形数据结构，通常分为最大堆和最小堆。在这个设计中，可以使用两个堆，一个最大堆存放较小的一半元素，一个最小堆存放较大的一半元素。新数插入时，根据其大小决定放入哪个堆。这样，保持堆的特性，插入操作的时间复杂度仍为O(logN)。当需要获取中位数时，如果元素总数为奇数，中位数就是最大堆的根节点；如果是偶数，中位数是最大堆的根节点和最小堆的根节点的平均值，查询时间复杂度为O(1)。 这样的设计巧妙地满足了题目要求，避免了维护整个序列的有序性，而是通过堆的特性保证了中位数的快速计算。通过堆，我们可以在不牺牲插入效率的情况下，实时获取数据流的中位数，实现了高效的数据结构设计。