java - 使用优先级队列计算中值

Question

我正在为 coursera 相关类(class)做这项作业，并且是 Java、DS 和 Algo 的新手。我不会在这里粘贴我的整个代码。但下面是我在相关代码中遇到的问题。

因此，为了检索中位数，我使用 PriorityQueue 和 Comparator 接口(interface)。从下面的函数中，我尝试创建两个 PriorityQueue，例如对于 21 个元素，hLow 优先级队列有 11 个最小元素，而 hHigh > 具有 10 个最高元素。

public static void addToStream (int k) {
    hLow.add (k);
    if (hLow.size() > (hHigh.size() + 1)) {
        hHigh.add(hLow.poll());
    }
}

我为hLow编写的比较器函数是

hLComp = new Comparator <Integer> () {
        public int compare (Integer o1, Integer o2) {
            return o1.compareTo(o2);
        }   
    };

对于hHigh是

hHComp = new Comparator <Integer> () {
        public int compare (Integer o1, Integer o2) {
            return -o1.compareTo(o2);
        }   
    };

我面临的问题是

hHigh.add(hLow.poll()) 

检索到错误的值。例如，如果第一个值是 3000，那么这就是中位数，但是当第二个值出现时，例如是 6000。然后代码进入 if 条件，之后 hHigh.peek 显示 3000 hLow.peek 显示 6000。这与我的预期相反。

Answer 1

上面的方法有问题。只要尝试 5 4 3 你就会看到。 该算法需要基本情况​​。这里解释得很好:

Find running median from a stream of integers