在小於線性時間的情況下從最小 - 最大隊列類中刪除最小值和最大值

Question

我正在實現具有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(); 

    } 
} 

Answer 1

甲min-max heap支持O（1）找到-最小值/最大值，和O（log n）的刪除最小/最大。 番石榴的MinMaxPriorityQueue是min-max堆的實現。

java標準庫中沒有min-max堆實現。如果你不能使用第三方庫，並且你不想實現你自己的min-max堆。您可以嘗試TreeSet，這是基於紅黑樹實施的。它有O（logn）delete-min/max，折衷find-min/max也是O（logn）。您可以嘗試使其threaded跟蹤最小/最大值，但需要對TreeSet進行大量更改。

如果您堅持使用兩個PriorityQueues來實現您的最小 - 最大隊列。您可以將其他隊列的所有元素索引保存到HashMap中，如the answer。因爲PriorityQueue＃removeAt（index）是O（logn）。但是每個元素移動都需要更新HashMap。我強烈建議不要這樣做，因爲額外的空間使用和可能表現不佳。