How do I use a TreeSet in Java that allows Duplicates?

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?

For example you can add a running ID to make sure you have no duplicates — Doron Yakovlev Golani, May 08 '17 at 15:19
The *entire point* of a set, in Java or anywhere else, is that it doesn't allow duplicates. — chrylis -cautiouslyoptimistic-, May 08 '17 at 15:20
If you want to insert duplicates then create a datastructure and insert its object.In this way it allows duplicates — Bharat, May 08 '17 at 16:49

Sanket Makani · Answer 1 · 2017-05-08T15:25:30.500

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

`insert` can be implemeted as just `map.merge(value, 1, Integer::sum)`, `removeHead` would be more efficient with `map.compute()` — Vadzim, May 28 '19 at 18:52
This answer is incorrect, because the question says delete a specific element in `O(logn)` time. Not just the head. PriorityQueue can delete ONLY head in `O(logn)` time. For a generic element deletion it takes `O(n)` time. — Pardhu, Aug 23 '22 at 07:59

score 2 · Answer 2 · edited May 23 '17 at 11:47

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.

How do I use a TreeSet in Java that allows Duplicates?

2 Answers2

Linked