如何追踪动态扩容数组的中位数？最优解决方案探讨

数组法 #

每次插入新元素时，通过二分查找确定它在有序数组中的插入位置，然后将元素插入并保持数组整体有序。

• 取中位数：直接根据数组长度，奇数时取中间索引的元素，偶数时取中间两个元素的平均值。
• 优点：实现简单，无需复杂数据结构，适合小规模数据场景。
• 缺点：插入操作需要移动后续元素，时间复杂度为O(n)，数据量较大时性能会明显下降。

二叉搜索树法 #

使用平衡二叉搜索树（如AVL树、红黑树）来存储元素，每个节点额外记录其子树的节点总数。

• 插入逻辑：按照二叉搜索树规则插入元素，同时维护树的平衡，确保左右子树高度差不超过1。
• 取中位数：根据总节点数，通过子树节点数快速定位到中间节点（奇数时是第(n+1)/2个元素，偶数时是第n/2和n/2+1个元素的平均值）。
• 优点：插入和查找中位数的时间复杂度均为O(logn)，性能稳定。
• 缺点：实现复杂度高，需要手动处理树的旋转平衡逻辑；若语言自带的有序集合不支持重复元素，还需额外处理重复值的存储。

双堆法 #

这是工业界最常用的方案，核心是维护两个堆：

• 一个大顶堆：存储数组中较小的一半元素，堆顶是这部分的最大值。
• 一个小顶堆：存储数组中较大的一半元素，堆顶是这部分的最小值。
• 插入规则：
  1. 若新元素小于等于大顶堆堆顶，插入大顶堆；否则插入小顶堆。
  2. 调整两个堆的大小，确保大顶堆的元素数量最多比小顶堆多1，或两者数量相等。
• 取中位数：
  1. 若两个堆大小相等，中位数为两个堆顶元素的平均值。
  2. 若大顶堆多一个元素，中位数就是大顶堆的堆顶。
• 优点：插入和取中位数的时间复杂度均为O(logn)，实现难度远低于平衡二叉树，逻辑清晰易懂。
• 缺点：需要同时维护两个堆，对堆的基本操作（插入、弹出）有一定的代码要求。

内容的提问来源于stack exchange，提问作者notaorb