数据流中实时中位数：堆结构优化

本课程设计报告针对的是广州大学计算机科学与网络工程学院计算机系17级软件工程专业1班学生谢金宏（学号1706300001，班内序号02）完成的项目，主题为"随时找到数据流中的中位数"。该任务要求设计一个名为MedianHolder的结构，能够在数据流中实时地计算并获取中位数，同时保持高效的时间复杂度。 在设计过程中，首先分析了两种常见的数据结构，顺序存储（数组）和链式存储（链表），以及它们在插入新数和查询中位数时的时间复杂度。顺序存储虽然简单，但插入和查询的时间复杂度分别达到O(log n)和O(n)，无法满足题目对插入操作时间复杂度的要求，即O(1)。链式存储虽然插入时间较快，但同样不满足查询中位数的要求。 因此，转而考虑采用非线性数据结构，如二分搜索树，虽然可以保持O(log n)的插入时间，但查询中位数的时间复杂度会提升到O(n)，也不是理想选择。问题的关键在于，实际上我们只需要在任何时刻快速找到一个数，它既不大于一半的数据，也不小于另一半，而不需要整个数据流保持有序。 这启发了设计者利用堆（优先队列）作为数据结构。具体来说，设计了两个堆：一个大顶堆（MaxHeap）和一个小顶堆（MinHeap）。大顶堆的性质是堆顶元素不大于小顶堆的堆顶，且大顶堆的元素数量最多比小顶堆多1。插入新数时，根据新数与小顶堆堆顶的比较结果，将数放入对应堆中，并保持堆的性质。这样，插入操作的时间复杂度为O(1)，因为只需调整堆的结构，而查询中位数的过程可以通过以下步骤实现： 1. 如果两个堆的大小不同，那么中位数位于较小堆的堆顶。 2. 如果两个堆的大小相同，中位数则是大顶堆和小顶堆堆顶的平均值，或者是一个堆顶，取决于数据流的最新状态。 通过使用堆，MedianHolder结构成功地实现了在任意时刻插入新数的时间复杂度为O(1)，并且查询中位数的时间复杂度也为O(1)，满足了题目要求。这样的设计充分考虑了实际应用场景的需求，避免了不必要的数据排序，提高了性能。