CODEWITHSUNDEEP
javaperformancesortingdata-structures
BaltoStar
BaltoStar

Reputation: 8987

Java data-structure maintaining sort order while enforcing max elements

does there exist a Java data-structure that :

  1. enforces max elements
  2. maintains sort order

so for list containing max n elements if a new element is added and belongs in top n then lowest-ranked element is evicted and re-sort is performed

what are the performance characteristics ?

could a better solution be obtained by crafting a custom solution using an underlying array ?

Upvotes: 0

Views: 433

Answers (3)

ravthiru
ravthiru

Reputation: 9633

You can also implement using PriorityQueue.

  1. Add elements until you reach max limit by checking size();

  2. After that you can use peek() to check if element has to be added or not, if you want to add then remove the lowest element and and then add new element. O(log(n)) time for poll(), remove() methods and constant time for peek() and size()

Upvotes: 0

CodeBlind
CodeBlind

Reputation: 4569

You could very quickly implement this using a TreeSet, a data structure that automatically stays sorted at all times.

To evict the lowest member, just call treeSet.pollFirst() whenever treeSet.size() is greater than your pre-defined maximum.

As for performance, TreeSet adds and removes run in O(log(n)) time. Maintaining sorted-ness with an array while supporting adds and removes would be much slower.

Upvotes: 1

user4752891
user4752891

Reputation:

You should consider using a TreeSet. Data is added there automatically in a sorted manner.

Upvotes: 3

Related Questions