CODEWITHSUNDEEP
javaalgorithm
Houcheng
Houcheng

Reputation: 2894

Is there a data structure in JDK that can remove, find and insert in log-N time?

After testing on RDring, I found that remove element sometime fails and the time complexity to remove a timer is linear; the alarm manager uses a TreeSet that iterate all elements for deleting.

Then, I look source of PriorityQueue and guess maybe can use it to store timer list. But I am very surprised that, though the deleting in PriorityQueue is in constant time, the inserting of an element in Priority queue is also linear. They didn't use any tree or something binary search technique to speed up the insertion.

If I want to remove fast, then PQ but insert slow. Otherwise I can use TreeSet for insert in log-N but delete slow. Is there any tree or heap that support both insert, delte and find in log-N speed ?

Upvotes: 2

Views: 800

Answers (1)

Andreas Fester
Andreas Fester

Reputation: 36650

Is there any tree or heap that support both insert, delete and find in log-N speed ?

Yes, the Red-Black tree based TreeMap guarantees that:

Class TreeMap<K,V>

...

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

See also

By the way, you say that with TreeSet, delete is slow - however, the JavaDoc also documents O(log(n)) for delete:

Class TreeSet<E>

...

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

Upvotes: 7

Related Questions