0

我正在实现一个同时具有 popMin 和 popMax 方法的队列类。到目前为止，我已经使用两个优先级队列，但即使删除是 log(n) 时间，我也必须从另一个队列中删除，这是线性的。我知道可以使用二进制堆来实现双端优先级队列，但是如果我没记错的话，这需要线性时间来构建吗？有没有办法可以更有效地做到这一点？我也只能使用 Java 库类。

static class MinMaxQueue {

    PriorityQueue<String> MinQueue = new PriorityQueue<String>(); 
    PriorityQueue<String> MaxQueue = new PriorityQueue<String>(Collections.reverseOrder()); 


    void push(String val) {
        MinQueue.add(val); 
        MaxQueue.add(val); 
    }

    String popMin() {
        MaxQueue.remove(MinQueue.peek()); 
        return MinQueue.remove();
    }

    String popMax() {
        MinQueue.remove(MaxQueue.peek()); 
        return MaxQueue.remove(); 
    }

    int size() {
        return MinQueue.size(); 

    }
}
4

1 回答 1

3

min-max 堆支持O(1) find-min/max 和 O(log n) delete-min/max。Guava 的MinMaxPriorityQueue是 min-max 堆的一种实现。

java标准库中没有最小-最大堆实现。如果您不能使用 3rd 方库，并且您不想实现自己的最小最大堆。您可以尝试基于Red-Black tree实现的TreeSet。它有 O(logn) delete-min/max，权衡是 find-min/max 也是 O(logn)。您可以尝试使其线程化以跟踪最小值/最大值，但需要对TreeSet进行大量更改。

如果你坚持使用两个PriorityQueues来实现你的 min-max 队列。您可以将其他队列的元素的所有索引跟踪到 HashMap 中，作为答案。因为 PriorityQueue#removeAt(index) 是 O(logn)。但是每个元素的移动都需要更新 HashMap。我强烈建议不要这样做，因为会占用额外的空间并且性能可能很差。

于 2016-06-08T03:13:30.700 回答