Hi everyone

I'm looking for any ideas on Incremental Deletion with the min() aggregate. This is not a homework question if you're wondering. ;) Anyways, here it goes:

Let's say that we have a set of numbers and a data structure is used to store the minimum value such it can be recalculated after incremental deletion. In other words, if I've got one billion values, I don't want to rescan all of them to find the minimum.

I thought of storing the values in a binary search tree as the set grows. When a value is removed the minimum is just the left most leaf. It will not be O(logn) if it's not balanced however. I'm wondering if anyone has a better idea. ;)

Thank you :p

Tim