如何在支持任意删除的动态数据流中高效维护中位数？

针对支持插入和任意删除的中位数维护需求，以下是几种满足复杂度要求的实现策略：

1. 平衡二叉搜索树（BST）+ 中位数指针 #

• 核心思路：利用平衡BST的有序性和O(log n)的插入/删除特性，同时维护指针快速定位中位数。对于允许重复元素的场景，使用支持重复键的平衡BST（如C++的multiset、Java的TreeSet配合计数映射）。
• 操作细节：
  • 维护两个指针：left_ptr指向左半部分的最大元素，right_ptr指向右半部分的最小元素。
  • 插入/删除元素后，根据元素总数的奇偶性和操作位置，调整两个指针的位置，确保其始终指向中位数相关节点。
  • 获取中位数：元素总数为奇数时，取left_ptr（或right_ptr）指向的元素；偶数时取两者的平均值。
• 时间复杂度：
  • 插入/删除：O(log n)
  • 获取中位数：O(1)
• 优缺点：依赖语言内置平衡BST时实现简单，但部分语言（如Python）无原生支持，需自行实现或依赖第三方库。

2. 延迟删除双堆结构 #

• 核心思路：基于经典双堆（大顶堆存左半元素，小顶堆存右半元素），引入延迟删除机制解决任意元素删除问题。用哈希表delete_count记录元素的待删除次数，当堆顶元素存在待删除标记时，持续弹出无效元素直到堆顶有效。
• 操作细节：
  • 插入：按经典双堆规则插入（保持左堆大小≥右堆，且左堆最大元素≤右堆最小元素），时间O(log n)。
  • 删除：在delete_count中增加对应元素的待删除次数（O(1)）；后续调整堆平衡或获取中位数前，清理堆顶无效元素，这一步均摊时间为O(log n)。
  • 获取中位数：先清理两堆堆顶无效元素，再根据堆大小取左堆顶（奇数个元素）或两堆顶平均值（偶数个元素），O(1)（清理代价已计入删除操作的均摊时间）。
• 时间复杂度：
  • 插入：O(log n)
  • 删除：均摊O(log n)
  • 获取中位数：O(1)（均摊）
• 优缺点：无需依赖平衡BST，仅用堆和哈希表即可实现，适配多数编程语言；缺点是存在一定空间开销，堆中会暂时保留无效元素。

3. 跳表（Skip List）+ 中位数指针 #

• 核心思路：跳表是支持O(log n)插入、删除和随机访问的有序结构，通过维护中位数指针快速获取结果。
• 操作细节：
  • 插入/删除元素时按跳表规则操作，完成后根据元素总数变化调整中位数指针位置。
  • 获取中位数：直接访问中位数指针指向的元素，或取相邻两元素的平均值。
• 时间复杂度：
  • 插入/删除：O(log n)
  • 获取中位数：O(1)
• 优缺点：性能与平衡BST相当，但手动实现复杂度较高，适合需要自定义有序结构的场景。

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