build data structure using build insert and median

Question

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)

Please show your own attempts at a solution, not dump your homework here. Please refer to [help] for more details, but what you're describing is a [self balancing binary-search tree](https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree) — OneCricketeer, Oct 13 '21 at 22:09
Please provide details for `Build()`. Is that building with data like {5,5, 2,2, 9,9, 3,3, 5,5, 0,0, -1, -1}? — chux - Reinstate Monica, Oct 13 '21 at 22:13
yes we assume that all elements are integer numbers from 1 to 10^6 — Redman, Oct 13 '21 at 22:15
@don'ttalkjustcode Well, a heap can be defined in a array, but I suppose you're correct that the initial build out for a balancing tree would be `O(n*logn)` — OneCricketeer, Oct 13 '21 at 22:19
@OneCricketeer Yeah, the "balancing" in "self balancing binary-search tree" isn't a problem, the "search" is :-). Heaps are the way to go here, I'd say. — no comment, Oct 13 '21 at 22:23
@don'ttalkjustcode The "search" function isn't wanted. The median of a balanced tree is always the root (or plus the left/right node, and divided by 2) — OneCricketeer, Oct 13 '21 at 22:29
@OneCricketeer I mean when you said "self balancing binary-search tree", the problem with that is that you can't build a BST in O(n) time because the searching requires sortedness. — no comment, Oct 13 '21 at 22:32
@OneCricketeer Yeah just realized. I still doubt the median is always at the root, though. — no comment, Oct 13 '21 at 22:34
@don'ttalkjustcode Yeah... (example on the page would be 23). In any case, [median can be found while building](https://stackoverflow.com/questions/33964676/find-the-median-of-an-unsorted-array-without-sorting), but not sure about after an insert happens — OneCricketeer, Oct 13 '21 at 22:38
@OneCricketeer Ha, right, I just pointed to the wrong picture :-). So... you're still trying the BST route? — no comment, Oct 13 '21 at 22:44

score 0 · Accepted Answer · answered Oct 13 '21 at 23:24

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.

build data structure using build insert and median

1 Answers1