build data structure using build insert and median-CodePudding

Consider the following operations

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).

How can i describe a data structure i.e provide an invariant that i will maintain in this data structure? How can i write the pseudocode for Build(), Insert() and Median()?

UPDATE
Build 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);
    }

This will both run in O(n).

Insert:

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

This will run in O(log n).

What about median? for run time O(1)

CodePudding user response：

Build: Use median-of-medians to find the initial median in O(n), use it to partition the values in half. The half with the smaller values goes into a max-heap, the half with the larger values goes into a min-heap, build each in time O(n). We'll keep the two heaps equally large or differing by at most one element.

Median: The root of the bigger heap, or the mean of the two roots if the heaps have equal size.

Insert: Insert into the bigger heap, then pop its root and insert it into the smaller heap.