We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Clean solution in Java 8 following the approach with 2 priority queues
classHeap{privateQueue<Integer>low=newPriorityQueue<>(Comparator.reverseOrder());privateQueue<Integer>high=newPriorityQueue<>();publicvoidadd(intnumber){Queue<Integer>target=low.size()<=high.size()?low:high;target.add(number);balance();}privatevoidbalance(){while(!low.isEmpty()&&!high.isEmpty()&&low.peek()>high.peek()){IntegerlowHead=low.poll();IntegerhighHead=high.poll();low.add(highHead);high.add(lowHead);}}publicdoublemedian(){if(low.isEmpty()&&high.isEmpty()){thrownewIllegalStateException("Heap is empty");}else{returnlow.size()==high.size()?(low.peek()+high.peek())/2.0:low.peek();}}}
Heaps: Find the Running Median
You are viewing a single comment's thread. Return to all comments →
Clean solution in Java 8 following the approach with 2 priority queues