如何在Java中使用允許重複的TreeSet？

Question

我想在O（LOGN）的時間與優先級隊列功能的數據結構，還能夠刪除一定不是在O（LOGN）時間的頭一個特定的元素。我聽說java中的TreeSet做了它，但不允許重複，我如何解決這個問題？

Answer 1

使用TreeMap它允許插入在log n時間和刪除log n時間。您可以在那裏存儲TreeMap<Integer,Integer>其中密鑰存儲元素的值，值存儲元素的頻率。

如果你需要做的只是Insert和Delete操作，使用Java的Priority Queue。它也允許在log n時間插入和刪除在log n時間，因爲它使用Heaps來存儲數據。

通過執行TreeMap的功能，您可以執行Insertion，Deletion。

TreeMap<Integer,Integer> map=new TreeMap<Integer,Integer>(); 

插入：

public boolean insert(int value) throws Exception 
{ 
    try 
    { 
     if(!map.containsKey(value)) 
      map.put(value,0); 

     map.put(value,map.get(value)+1); 

     return true; 
    } 
    catch(Exception e) 
    { 
     e.printStackTrace(); 
     return false; 
    } 
} 

頭隊列（PEEK）：

public int getHead() 
{ 
    if(map.firstKey()==null) 
     return null; 

    return (int)map.firstKey(); 
} 

刪除和檢索頭（輪詢）：

public int removeHead() 
{ 
    if(getHead()==null) 
     return null; 

    int head=getHead(); 

    if(map.get(head)==1) 
     map.remove(head); 
    else 
     map.put(head,map.get(head)-1); 
} 

Answer 2

我沒有足夠的信譽發表評論，所以我會在這裏說這個。我認爲按照here的說明去除優先隊列中的元素是O（N）。

你也許能夠解決這個問題在某些情況下。如果您不打算在刪除對象後添加對象，則可以對priorityqueue進行封裝並保留已刪除元素的散列集。然後，如果您在輪詢時遇到該對象，則將其丟棄。

你也可以使用一個有序列表創建自己的PriorityQueue。然後，您可以使用二進制搜索來查找插入位置或要有效刪除的索引。