How to effectively track the smallest item in a collection?

Question

In the spirit of programming issues: suppose that there is a set of objects that can be compared with each other and sorted. What is the most efficient way to track the smallest item in a collection as objects are added and the current smallest is occasionally deleted?

Answer 1

Using a mini-heap is the best way.

http://en.wikipedia.org/wiki/Heap_(data_structure)

It is intended for this application.

Answer 2

@Harpreet
This is not optimal. When an object is deleted, erickson will have to scan the entire collection to find the new smallest.

You want to read the binary search tree . MS has a good website to get started. But you might want to get a book, for example, Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) , if you want to dive deep.

Answer 3

If you need random insertion and deletion, the best way is probably a sorted array. Insertions and deletions must be O (log (n)).

Answer 4

For accidentally deleting a Fibonacci Heap, even faster than the minimum heap. The insert is O (1), and the min search is also O (1). Removal - O (log (n))

Answer 5

If you need random insertion and deletion, the best way is probably to sort the array. Insertions and removals should be O (log (n)).

Yes, but you will need to re-sort each insert and (possibly) each delete, which, as you said, is O (log (n)).

With the solution proposed by Harprit:

• you have one O (n) pass at the beginning to find the smallest element
• the insert is O (1) after that (only one comparison is needed for the smallest element already known)
• delete will be O (n) because you will need to find the smallest element (remember that Big O notation is the worst case). You can also optimize by checking to see if the item you want to remove is the smallest, and if not, just do not double-check to find the smallest item.

So it depends. One of these algorithms would be better for an insert-heavy use case with multiple deletions, but the other is generally more consistent. I think that I would use Harpreet's mechanism by default if I didn’t know that the smallest number would be deleted often, because this provides a weak point in this algorithm.

Answer 6

Harpreet:

inserts into this will be linear, since you need to move the elements to insert.

Doesn’t it depend on the implementation of the collection? If it acts as a linked list, the insert will be O (1), and if it were implemented as an array, it would be linear, as you said.

Answer 7

Depends on what operations you need to support your container. A min-heap is best if you might need to remove the min element at any given time, although several operations are nontrivial (amortized log (n) time in some cases).

However, if you only need to press / pop from the front / back, you can simply use a mind that allows you to amortise constant time for all operations (including findmin). You can do a scientific search to find out more about this structure. Recently, we worked with a friend to achieve a much simpler, more understandable and thoughtful version of mindeque. If this is what you are looking for, I can post the details for you.