Heaps: Find the Running Median

  • + 11 comments

    Clean solution in Java 8 following the approach with 2 priority queues

    class Heap {
        private Queue<Integer> low = new PriorityQueue<>(Comparator.reverseOrder());
        private Queue<Integer> high = new PriorityQueue<>();
    
        public void add(int number) {
            Queue<Integer> target = low.size() <= high.size() ? low : high;
            target.add(number);
            balance();
        }
    
        private void balance() {
            while(!low.isEmpty() && !high.isEmpty() && low.peek() > high.peek()) {
                Integer lowHead= low.poll();
                Integer highHead = high.poll();
                low.add(highHead);
                high.add(lowHead);
            }
        }
    
        public double median() {
            if(low.isEmpty() && high.isEmpty()) {
                throw new IllegalStateException("Heap is empty");
            } else {
                return low.size() == high.size() ? (low.peek() + high.peek()) / 2.0 : low.peek();
            }
        }
    }