Удаление min и max из класса очереди min-max менее чем за линейное время

Question

Я реализую класс очереди, который имеет метод popMin и popMax. До сих пор он работал с двумя приоритетными очередями, но, хотя время удаления - это время журнала (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(); 

    }
}

Answer 1

Мин-макс куча поддерживает O(1) find-min/max и O(log n) delete-min/max. MinMaxPriorityQueue в Guava - реализация кучи min-max.

В стандартной библиотеке Java нет реализации кучи min-max. Если вы не можете использовать стороннюю библиотеку и не хотите реализовывать свою собственную кучу min-max. Вы можете попробовать TreeSet, который реализован на основе красно-черного дерева. У него есть O(logn) delete-min/max, компромисс между находкой-min / max и O(logn). Вы можете попробовать сделать так, чтобы он отслеживал мин / макс, но требует много изменений в TreeSet.

Если вы используете две PriorityQueues для реализации своей очереди min-max. В качестве ответа вы можете отслеживать все индексы элементов другой очереди в HashMap. Потому что PriorityQueue #removeAt(index) - это O(logn). Но каждое движение элемента требует обновления HashMap. Я настоятельно рекомендую не делать этого из-за дополнительного использования пространства и, вероятно, низкой производительности.