实现支持O(n)构建、O(logn)插入、O(1)求中位数的数据结构

核心维护不变量 #

我们用两个堆共同存储所有元素，始终满足以下规则：

• 大顶堆low：存储所有小于等于中位数的元素，堆顶为这部分元素的最大值
• 小顶堆high：存储所有大于等于中位数的元素，堆顶为这部分元素的最小值
• 堆大小约束：要么size(low) = size(high)（元素总数为偶数），要么size(low) = size(high) + 1（元素总数为奇数）

各操作实现 #

Build(A[1..n]) 时间复杂度O(n) #

利用题目给出的O(n)建堆能力，结合O(n)复杂度的快速选择算法完成初始化：

Build(A):
    n = length(A)
    m = (n + 1) // 2
    // 快速选择找到数组中第m小的元素作为分界，时间复杂度O(n)
    pivot = quick_select(A, m)
    // 拆分元素到两个堆的底层数组
    low_arr = 所有小于等于pivot的元素，取前m个
    high_arr = 所有大于pivot的元素，补充low_arr剩下的等于pivot的元素凑齐n-m个
    // 调用题目提供的O(n)建堆函数
    build_maxheap(low_arr)
    build_minheap(high_arr)
    low = low_arr
    high = high_arr

Insert(x) 时间复杂度O(log n) #

插入后调整堆大小满足不变量，所有堆操作均为O(log n)：

Insert(x):
    if low为空 or x <= max_heap_top(low):
        insert(low, x) // 调用题目提供的大顶堆插入函数
    else:
        insert(high, x) // 调用题目提供的小顶堆插入函数
    
    // 调整堆大小满足不变量
    if size(low) > size(high) + 1:
        // 弹出大顶堆最大值插入小顶堆
        max_val = extract_max(low)
        insert(high, max_val)
    elif size(high) > size(low):
        // 弹出小顶堆最小值插入大顶堆
        min_val = extract_min(high)
        insert(low, min_val)

Median() 时间复杂度O(1) #

直接读取堆顶元素即可，无需遍历：

Median():
    if (size(low) + size(high)) % 2 == 1:
        return max_heap_top(low)
    else:
        // 若要求取整数中位数可返回low堆顶，此处返回平均值为通用实现
        return (max_heap_top(low) + min_heap_top(high)) / 2

题目提供的已有基础实现 #

// 大顶堆构建，时间复杂度O(n)
void build_maxheap (int Arr[ ])
{
    for(int i = N/2 ; i >= 1 ; i-- )
    {
        max_heapify (Arr, i) ;
    }
}

// 小顶堆构建，时间复杂度O(n)
void build_minheap (int Arr[ ]) 
{
    for( int i = N/2 ; i >= 1 ; i--)
        min_heapify (Arr, i);
}

// 堆插入操作，时间复杂度O(log n)
void insert (int Arr[ ], int val)
{
    length = length + 1;
    Arr[ length ] = -1;  
    increase_val (Arr, length, val);
}

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