Data Structures – Sorting by Multiple Attributes

See https://stackoverflow.com/q/5527437/10396 for an implementation of a rolling median that uses a min-max heap to process each new sample in O(lgN). The heap keeps the data loosely sorted into two groups, one bigger than the median, one smaller. For each new sample, it swaps the the oldest item in the heap with the newest one. Rebalancing the heap takes up to 2 O(lgN) steps: a sift-up to make sure the new item is closer to the median than any parents, and maybe a sift-down to push it down the other side.

Ditch the recursion. You usually need recursion when dealing with trees because you need to visit all the paths, but here you only visit one child in each level - you can do it with a loop. Also, while your code looks like it can update nodes at any level while going up the recursion, it actually only changes one node - the parent of the node with minimal value. Since you detect that that node needs to be change one level after you visit it(when you reach the end of the leftmost path) you don't need to bubble that up - you can just keep the parent level in a variable:

public int removeMin() {
    if (root == null) { //if Queue is empty
        System.out.println("Queue is empty");
        return 0;
    }

    if (root.left == null) { // Edge case - no left child, root is the min
        int min = root.key;
        if (root.right == null) {
            root = null;
        } else {
            root = root.right;
        }
        return min;
    }

    // Start going left
    Node parent = root;
    Node node = parent.left;

    while(node.left != null) {
        parent = node;
        node = parent.left;
    }

    // node.left is null, so node is the min
    parent.right = node.right; // which could be null - it works either way
    return node.key;
}