在小于线性时间内从最小-最大队列 class 中删除最小值和最大值

Question

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

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(); 

    }
}

Answer 1

A min-max heap 支持 O(1) find-min/max 和 O(log n) delete-min/max。 Guava 的 MinMaxPriorityQueue 是最小-最大堆的实现。

java 标准库中没有最小-最大堆实现。如果您不能使用 3rd 方库，并且不想实现自己的最小-最大堆。您可以尝试 TreeSet which is implemented based on Red-Black tree. It has O(logn) delete-min/max, the trade-off is find-min/max is O(logn) as well. You can try make it threaded 来跟踪 min/max，但需要对 TreeSet.

进行大量更改

如果您坚持使用两个 PriorityQueues 来实现您的最小-最大队列。您可以将另一个队列的元素的所有索引跟踪到一个 HashMap 中，如 the answer。因为 PriorityQueue#removeAt(index) 是 O(logn)。但是每个元素移动都需要更新 HashMap。我强烈建议不要这样做，因为额外的 space 用法和可能很差的性能。

在小于线性时间内从最小-最大队列 class 中删除最小值和最大值

Deleting min and max from min-max queue class in less than linear time

java

queue

big-o

minmax-heap