Efficient data structure for finding median

Just come up with a relatively simple implementation for a data structure that can report median value in constant time, and insertion/remove median in O(log(n)) time. It uses a max heap and min heap to store elements that are smaller and larger then the median respectively, and maintains the property that the differences between the two heaps are always less than or equal to 1.

Feel free to use/enhance/comment it.

import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Data structure for storing collection of elements which can report
 * median in constant time, while {@linkplain FastMedian#add(java.lang.Object) adding} 
 * new element and {@linkplain FastMedian#removeMedian() remove median} takes O(log(n)) time. 
 * If there are even number of elements, it always
 * uses the smaller of the two median numbers as the median value.
 */
public class FastMedian<T> {
    private final Comparator<? super T> comparator;
    private final Queue<T> maxHeap;
    private final Queue<T> minHeap;
    private T median;

    /**
     * Creates a {@code FastMedian} which order elements according to their
     * {@linkplain Comparable natural ordering}.
     */
    public FastMedian() {
        this(null);
    }

    /**
     * Creates a {@code FastMedian} which order elements according to the given
     * {@link Comparator}.
     * 
     * @param comparator the comparator for ordering elements. If {@code null},
     *        the {@linkplain Comparable natural ordering} will be used.
     */
    public FastMedian(Comparator<? super T> comparator) {
        this.comparator = comparator;
        if (comparator == null) {
            this.maxHeap = new PriorityQueue<T>(11, Collections.reverseOrder());
            this.minHeap = new PriorityQueue<T>();
        } else {
            this.maxHeap = new PriorityQueue<T>(11, Collections.reverseOrder(comparator));
            this.minHeap = new PriorityQueue<T>(11, comparator);
        }
    }

    /**
     * Inserts the given element.
     *
     * @param e the element to add.
     */
    public void add(T e) {
        if (median == null) {
            median = e;
            return;
        }
        int cmp = (comparator == null) ? (((Comparable<? super T>) e).compareTo(median)) : comparator.compare(e, median);
        if (cmp < 0) {
            maxHeap.add(e);
        } else {
            minHeap.add(e);
        }
        // Rebalance
        int sizeDiff = maxHeap.size() - minHeap.size();
        if (sizeDiff > 0) {
            minHeap.add(median);
            median = maxHeap.remove();
        } else if (sizeDiff < -1) {
            maxHeap.add(median);
            median = minHeap.remove();
        }
    }

    /**
     * Returns the current median value.
     *
     * @return current median value.
     */
    public T getMedian() {
        return median;
    }

    /**
     * Removes the current median and returns it.
     *
     * @return value of the median removed.
     */
    public T removeMedian() {
        T result = median;
        if (maxHeap.isEmpty() && minHeap.isEmpty()) {
            median = null;
            return result;
        }
        if (maxHeap.size() >= minHeap.size()) {
            median = maxHeap.remove();
        } else {
            median = minHeap.remove();
        }
        return result;
    }    
}

A very simple example on using it:


import java.util.TreeSet;

public class MedianTest {
    
    public void test() {
        TreeSet<Integer> numbers = new TreeSet<Integer>();
        FastMedian<Integer> fastMedian = new FastMedian<Integer>();
        
        for (int i = 1; i < 10; i += 2) {
            numbers.add(i);
            fastMedian.add(i);
            System.out.println(numbers + " median: " + fastMedian.getMedian());
        }
        
        for (int i = 10; i >= 2; i -= 2) {
            numbers.add(i);
            fastMedian.add(i);
            System.out.println(numbers + " median: " + fastMedian.getMedian());
        }
        
        System.out.println();

        Integer median = fastMedian.removeMedian();
        while (median != null) {
            numbers.remove(median);
            System.out.println(numbers + " removed: " + median + " new median: " + fastMedian.getMedian());
            median = fastMedian.removeMedian();
        }
    }
}

Building a Great Team (via Ship Software OnTime!)

Can’t help to reblog this old post.

Building a Great Team The centerpiece of any successful development project is the team that builds it. There is no other single most important contributing factor to building great products. No tools, no development methods, no amount of money and no amount of time can substitute for the importance of an exceptional team if you plan to create an exceptional product. Some in our industry operate under the assumption "with a good system and a fine-tuned set of processe … Read More

via Ship Software OnTime!