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