fill median of number in arrays

Question

We have array arr with n distinct elements. we want to fill D[i] be median of numbers arr[1] to arr[i]. it can done efficiently in O(n log n).

Is there any effective way that we do this work?

Answer 1

Supposing that array arr is already sorted in increasing order, the following code fills array D, where for each i, D[i] is the median of values (arr[0], ..., arr[i]).

// uncomment line below if arr is not sorted
// Arrays.sort(arr);

for (int i = 0, i < arr.length; i++)
{
    if (i % 2 == 0) {
        
        // calculate median for array with odd length
        D[i] = arr[i/2];
    }
    else {
        
        // calculate median for array with even length
        D[i] = (arr[i/2] + arr[i/2 + 1]) / 2;
    }  
}

Complexity: The time complexity for the above algorithm is O(n).

In case the initial array is not sorted and we have to sort it, this add time complexity O(nlogn). The final time complexity is O(nlogn + n) = O(nlogn)

Answer 2

Theta(n log n) complexity approach:

Make two heaps - maximal heap and minimal heap

Walk through array a and insert every element in two-heaps data structure.

If element is larger than currend median, add it to minimal heap (it contains larger elements), otherwise add it to maximal heap (with smaller elements)

Keep heaps of (almost) equal size ((k+1)/2 and k/2 at k-th step), moving top element into another heap if needed.

Median element of current slice is at the top of the larger heap

I hope it is enough to have these clues to implement.

Java (I've had to learn a bit ;))

public static void main (String[] args) throws java.lang.Exception
{  Integer[] arr= {10,70,4,15,20,12,8,17};
   PriorityQueue<Integer>maxheap = new PriorityQueue<>(10, Collections.reverseOrder());
   PriorityQueue<Integer>minheap = new PriorityQueue<>(10);
   Integer median = -9999;
   for (Integer a: arr) {
      if (a >= median) {
         minheap.add(a);
         if (minheap.size() - maxheap.size() >= 2)
             maxheap.add(minheap.poll());
      }
        else {
         maxheap.add(a);
         if (maxheap.size() - minheap.size() >= 2)
             minheap.add(maxheap.poll());
        } 
        Integer diff = maxheap.size() - minheap.size();
        if (diff == 1)
             median = maxheap.peek();
        else if (diff == -1)
           median = minheap.peek();
        else   
            median = Math.min(minheap.peek(), maxheap.peek());
        System.out.println(median);
   }
}

Python implementation (first done). Minus is used to provide correct ordering of max heap (Python heapq is minimal heap) without additional comparator.

import heapq

arr=[10,70,4,15,20,12,8,17]
print(arr)
d = []
ds = []
minheap = []
maxheap = []
median = -99999
for i in range(len(arr)):
    sli = arr[:i+1]
    sli.sort()
    ds.append(sli[(len(sli) - 1)//2])

    if arr[i] >= median:
        heapq.heappush(minheap, arr[i])
        if len(minheap) - len(maxheap) >= 2:
           heapq.heappush(maxheap, -heapq.heappop(minheap))
    else:
        heapq.heappush(maxheap, -arr[i])
        if len(maxheap) - len(minheap) >= 2:
           heapq.heappush(minheap, -heapq.heappop(maxheap))

    diff = len(maxheap) - len(minheap)
    if diff == 1:
        median = -maxheap[0]
    elif diff == -1:
        median = minheap[0]
    else:
        median = min(minheap[0], -maxheap[0])
    d.append(median)

print(ds) #dumb method to compare
print(d)

>>>[10, 10, 10, 10, 15, 12, 12, 12]
>>>[10, 10, 10, 10, 15, 12, 12, 12]