algorithm - 使用构建插入和中值构建数据结构

Question

考虑以下操作

Build(A[1 . . . n])：使用（可能未排序的）数组 A 的重复元素初始化数据结构。它在时间 O(n) 中运行。

Insert(x)：将元素 x 插入数据结构。它以 O(log n) 的时间运行。

中位数：返回当前存储元素的中位数1。它在 O(1) 时间内运行。

我如何描述一个数据结构，即提供一个我将在这个数据结构中维护的不变量？如何编写 Build()、Insert() 和 Median() 的伪代码？

更新
构建最大堆/最小堆：

void build_maxheap (int Arr[ ])
    {
        for(int i = N/2 ; i >= 1 ; i-- )
        {
            max_heapify (Arr, i) ;
        }
    }

void build_minheap (int Arr[ ]) 
    {
        for( int i = N/2 ; i >= 1 ; i--)
        min_heapify (Arr, i);
    }

这都将在 O(n) 中运行。

插入：

void insert (int Arr[ ], int val)
    {
        length = length + 1;
        Arr[ length ] = -1;  
        increase_val (Arr, length, val);
    }

这将在 O(log n) 中运行。

中位数呢？运行时间 O(1)

标签： algorithmdata-structuresmedian

Answer 1

构建：使用中位数的中位数找到 O(n) 中的初始中位数，用它将值分成两半。具有较小值的一半进入最大堆，具有较大值的一半进入最小堆，每个都在 O(n) 时间内构建。我们将保持两个堆大小相等或最多相差一个元素。

中位数：较大堆的根，如果堆大小相等，则为两个根的平均值。

插入：插入到较大的堆中，然后弹出它的根并插入到较小的堆中。