Find dynamic median
  • runningtime
  • constanttime
  • median
  • logarithmictime
  • searching
  •   
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (2475)

Design a data structure that has the following properties :


  • Insertion in logarithmic time
  • Find median in constant time


Posted Answers

We can design the data structure using two heaps - one \( max \) heap and one \( min \) heap.

\( \underline {Insertion\ in\ logarithmic\ time} \) - When a new number is inserted, it is compared to the root of the \( max \) heap. If the new number is less than or equal to the root of the \( max \) heap it is placed into the \( max \) heap followed by heapify operation to find its position, otherwise in the \( min \) heap. Since heapify operation can be performed in logarithmic time, insertion can also be performed in logarithmic time.

\( \underline{Find\ median\ in\ constant\ time} \) -


  • If the number of elements in one of the heaps is greater than the other by more than \( 1 \), move the root of the heap containing more elements to the other one. If the two heaps have unequal number of elements, median will be the root of the heap with more elements.
  • If the two heaps contain exactly equal number of elements, median can be found by taking the mean of the two root
    elements, \( i.e, \) median = (root of the \( max \) heap + root of the \( min \) heap) / 2.

In either case, median can be found in constant time.

 
public static void InsertNewNumber(int n){

if(maxHeap.size() == minHeap.size()){
if((minHeap.peek()! = null) & & (minHeap.peek() < n)){
/* Move the root of minHeap to maxHeap and insert the new number
to minHeap */
maxHeap.offer(minHeap.poll());
minHeap.offer(n);
}
else{
/* If the new number is less than the root of maxHeap, move the
root of maxHeap to minHeap and insert the new number to minHeap */
if(maxHeap.peek() > n){
minHeap.offer(maxHeap.poll());
maxHeap.offer(n);
}
else
/* Insert the number in the minHeap */
minHeap.offer(n);
}
}
}


  public static int FindMedian(){

/* If maxHeap is empty return the root of minHeap */
if(maxHeap.isEmpty())
return minHeap.peek();

/* If minHeap is empty return the root of maxHeap */
if(minHeap.isEmpty())
return maxHeap.peek();

/* If the size of the two heaps are equal */
if(maxHeap.size() == minHeap.size())
return (maxHeap.peek() + minHeap.peek())/2;

/* If maxHeap has more elements than minHeap */
elseif(maxHeap.size() > minHeap.size())
return maxHeap.peek();

/* If minHeap has more elements than maxHeap */
else
return minHeap.peek();
}

You need to Sign In to post your solution.