CODEWITHSUNDEEP
javascalacollectionsguavascala-collections
davidrpugh
davidrpugh

Reputation: 4553

High performance Scala/Java collection needed

I am looking for a Scala (or Java/Guava) collection that supports O(1) access to (and ideally removal of) its minimum element as well as O(log n) insertion and removal of arbitrary elements.

Thoughts?

Upvotes: 0

Views: 219

Answers (2)

mfulton26
mfulton26

Reputation: 31214

PriorityQueue:

Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

This class is a member of the Java Collections Framework.

Upvotes: 5

celezar
celezar

Reputation: 442

Create your own collection backed by ArrayList. It needs additional fields minimum element and position of minimum element. Update those fields when you add element if that element is new minimum.

Upvotes: -1

Related Questions