Which sorted collection implementation has the smallest memory footprint in Java?

Question

I'm not unduly bothered about read/write performance (though obviously as fast as possible is always good), rather I'm looking for a sorted collection implementation that is as memory efficient as possible. Any suggestions?

Answer 1

Well then just store it in array of exactly the size you need, and sort it. one time work of O(n log n), and each search thereafter is O(log n). You can easily convrted the sorted array to a List with Arrays.asList().

Answer 2

Why not store them as Fibonacci Heaps? They're fast, small, and effective. If that's too complicated you can look at several other types of heap implementations. Many heaps can be stored as an array. This means you only need as much storage space as you have objects in your collection.

Answer 3

The very smallest sorted Collection is an ArrayList; it's not much bigger than the underlying array. The contents are sorted if you call sort() on them.

Answer 4

A TreeSet has decent memory conservation and for time performance offers O(log n) insert/lookup.

Answer 5

ImmutableSortedSet from google-collections is the smallest thing I know of to satisfy your requirement ("sorted collection implementation"), but is not modifiable.