使用 build insert 和 median 构建数据结构

Question

考虑以下操作

Build(A[1 . . . n]): Initialises the data structure with the elements of the (possibly unsorted)array A with duplicates. It runs in time O(n).

Insert(x): Inserts the element x into the data structure. It runs in runs in time O(log n).

Median: Returns the median1 of the currently stored elements. It runs in time O(1).

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

更新
构建 max-heap/min-heap：

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)

Answer 1

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

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

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

使用 build insert 和 median 构建数据结构

build data structure using build insert and median

algorithm

data-structures

median