How do I use a TreeSet in Java that allows Duplica

Question

I want a data structure with priority queue functions in O(logn) time and also be able to delete a specific element that's not necessarily the head in O(logn) time. I heard the TreeSet in java does it but does not allow Duplicates, How do i get around this?

Answer 1

Use TreeMap which allows insertion in log n time and deletion in log n time. You can have there TreeMap<Integer,Integer> where key stores the value of element and value stores the frequency of the element.

If you need to do only Insert and Delete operation , Use Java's Priority Queue. It also allows insertion in log n time and deletion in log n time as it uses Heaps to store the data.

You can do Insertion, Deletion by implementing the functions for TreeMap.

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

Insertion :

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;
    }
}

Head of the queue(peek) :

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

    return (int)map.firstKey();
}

Remove and retrieve head(poll) :

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

I don't have enough reputation to comment so i'll say this here. I think that removing an element in a priorityqueue is O(N) as stated here.

You might be able to get around this in some cases. If you don't plan on adding an object after removing it, you could make a wrapper around the priorityqueue and keep a hashSet of removed elements. Then, if you come across that object when polling, you discard it.

You could also create your own priorityqueue using an ordered list. You could then use a binary search to find insert positions or the index to remove efficiently.