data-structures - How do I efficiently keep track of the smallest element in a collection?

Question

In the vein of programming questions: suppose there's a collection of objects that can be compared to each other and sorted. What's the most efficient way to keep track of the smallest element in the collection as objects are added and the current smallest occasionally removed?

Answer 1

Using a min-heap is the best way.

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

It is tailor made for this application.

Answer 2

If you need random insert and removal, the best way is probably a sorted array. Inserts and removals should be O(log(n)).

Answer 3

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

You want to read up on Binary search tree's. MS has a good site to start down the path. But you may want to get a book like Introduction to algorithms (Cormen, Leiserson, Rivest, Stein) if you want to deep dive.

Answer 4

時折削除する場合、フィボナッチ ヒープは最小ヒープよりもさらに高速です。挿入は O(1) で、最小値を見つけるのも O(1) です。除去は O(log(n))

Answer 5

If you need random insert and removal, the best way is probably a sorted array. Inserts and removals should be O(log(n)).

Yes, but you will need to re-sort on each insert and (maybe) each deletion, which, as you stated, is O(log(n)).

With the solution proposed by Harpreet:

• you have one O(n) pass in the beginning to find the smallest element
• inserts are O(1) thereafter (only 1 comparison needed to the already-known smallest element)
• deletes will be O(n) because you will need to re-find the smallest element (keep in mind Big O notation is worst case). You could also optimize by checking to see if the element to be deleted is the (known) smallest, and if not, just don't do any of the re-check to find the smallest element.

So, it depends. One of these algorithms will be better for an insert-heavy use case with few deletes, but the other is overall more consistent. I think I would default to Harpreet's mechanism unless I knew that the smallest number would be removed often, because that exposes a weak point in that algorithm.

Answer 6

Harpreet:

the inserts into that would be linear since you have to move items for an insert.

Doesn't that depend on the implementation of the collection? If it acts like a linked-list, inserts would be O(1), while if it were implemented like an array it would be linear, as you stated.

Answer 7

Depends on which operations you need your container to support. A min-heap is the 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 push/pop from the front/back, you can just use a mindeque which achieves amortized constant time for all operations (including findmin). You can do a scholar.google.com search to learn more about this structure. A friend and I recently collaborated to reach a much easier-to-understand and -to-implement version of a mindeque, as well. If this is what you're looking for I could post the details for you.