如何向已排序列表添加元素并维持有序？附滑动窗口中位数优化需求

一、有序List<int>插入元素的现成工具与实现方式 #

现成结构选择 #

• 不需要重复元素的话，直接用SortedSet<int>即可，它会自动维护有序性，调用Add方法就能插入元素，时间复杂度为O(log n)。但要注意它不允许重复值，业务场景需要重复元素的话就用不了。
• 要支持重复元素的话，.NET没有直接的有序列表结构（SortedList<TKey,TValue>是键值对类型，键必须唯一），推荐用List<int>结合BinarySearch方法实现高效插入，代码示例如下：

public static void InsertSorted(List<int> list, int x)
{
    if (list.Count == 0 || x >= list[list.Count - 1])
    {
        list.Add(x);
        return;
    }
    int index = list.BinarySearch(x);
    // BinarySearch返回负数时，插入位置是对结果取反
    if (index < 0) index = ~index;
    list.Insert(index, x);
}

这里BinarySearch是O(log n)的时间复杂度，虽然List插入元素本身是O(n)（需要移动数组元素），但比遍历找插入位置的O(n)效率高不少。

二、滑动窗口求中位数的优化方案 #

你现在每次滑动后重新排序的做法时间复杂度是O(n log n)，对于大型列表和多次滑动的场景性能很差，更高效的方案是用双堆法，每次操作的时间复杂度降到O(log n)。

核心思路 #

维护两个堆：

• 最大堆：存储窗口中较小的一半元素，堆顶是这一半的最大值
• 最小堆：存储窗口中较大的一半元素，堆顶是这一半的最小值
  保持两个堆的大小差不超过1：
  • 窗口大小为奇数时，最大堆比最小堆多1个元素，中位数就是最大堆的堆顶
  • 窗口大小为偶数时，中位数是两个堆顶的平均值

具体实现要点（以.NET 6+的Heap<T>为例） #

因为直接从堆里删除指定元素是O(n)的时间复杂度，所以采用懒删除思路：用字典记录每个元素的计数，只有当堆顶元素的计数为0时，才弹出堆顶，避免实时删除堆中的元素。

简化代码示例

using System.Collections.Generic;

public class SlidingWindowMedian
{
    private readonly Heap<int> _maxHeap; // 用自定义比较器实现最大堆
    private readonly Heap<int> _minHeap;
    private readonly Dictionary<int, int> _elementCounts;
    private readonly int _windowSize;
    private int _currentCount;

    public SlidingWindowMedian(int windowSize)
    {
        _windowSize = windowSize;
        // 最大堆：降序比较器
        _maxHeap = new Heap<int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        _minHeap = new Heap<int>();
        _elementCounts = new Dictionary<int, int>();
    }

    // 添加新元素到窗口
    public void AddNewElement(int num)
    {
        // 把元素放到对应的堆里
        if (_maxHeap.Count == 0 || num <= _maxHeap.Peek())
        {
            _maxHeap.Push(num);
        }
        else
        {
            _minHeap.Push(num);
        }
        // 更新元素计数
        _elementCounts.TryAdd(num, 0);
        _elementCounts[num]++;
        _currentCount++;

        // 当窗口元素超过大小限制时，移除最左侧的元素
        // 这里需要结合你的滑动逻辑，传入要移除的旧元素，比如：
        // RemoveOldestElement(oldestNum);
    }

    // 移除窗口最左侧的元素
    public void RemoveOldestElement(int num)
    {
        _elementCounts[num]--;
        _currentCount--;

        // 清理堆顶的无效元素（计数为0的元素）
        CleanHeapTop(_maxHeap);
        CleanHeapTop(_minHeap);

        // 调整两个堆的大小平衡
        BalanceHeaps();
    }

    // 清理堆顶的无效元素
    private void CleanHeapTop(Heap<int> heap)
    {
        while (heap.Count > 0 && _elementCounts.TryGetValue(heap.Peek(), out int count) && count == 0)
        {
            heap.Pop();
        }
    }

    // 平衡两个堆的大小
    private void BalanceHeaps()
    {
        // 最大堆的大小不能比最小堆大超过1
        while (_maxHeap.Count - _minHeap.Count > 1)
        {
            int top = _maxHeap.Pop();
            _minHeap.Push(top);
            CleanHeapTop(_maxHeap);
        }
        // 最小堆的大小不能超过最大堆
        while (_minHeap.Count > _maxHeap.Count)
        {
            int top = _minHeap.Pop();
            _maxHeap.Push(top);
            CleanHeapTop(_minHeap);
        }
    }

    // 获取当前窗口的中位数
    public double GetMedian()
    {
        // 先清理堆顶无效元素
        CleanHeapTop(_maxHeap);
        CleanHeapTop(_minHeap);

        if (_windowSize % 2 == 1)
        {
            return _maxHeap.Peek();
        }
        else
        {
            return (_maxHeap.Peek() + _minHeap.Peek()) / 2.0;
        }
    }
}

注意事项 #

• 如果你的.NET版本低于6，没有内置的Heap<T>，可以自己实现一个堆结构，或者用PriorityQueue<TElement, TPriority>来模拟（最大堆可以用负数作为优先级）。
• 懒删除是这个方案的核心，它避免了直接操作堆的删除，保证了每次操作的时间复杂度是O(log n)。

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