I need to use a data structure, implementable in C++, that can do basic operations, such as lookup, insertion and deletion, in constant time. I, however, also need to be able to find the maximum value in constant time.
This data structure should probably be sorted to find the maximum values and I have looked into red-black trees, however they have logarithmic-time operations.
It is impossible to build a data structure that supports insert, maximum, and delete all in constant time. Such a data structure is a priority queue, and a priority queue with all constant-time operations can do heapsort in linear time. Since there is a superlinear lower bound on sorting, this is impossible. One of insert, maximum, or delete must be logarithmic time.
Certain species of tree (like those with lazy deletion and incremental partial rebuilding) require only insert to be linear time. A skew binomial heap requires only delete to be linear time.
I think we should start by clarifying a few things. The data structure is simply, as the name implies, the way in which the information is structured or organized. When you talk about performing operations such as searches, insertion, and deletions, you're really talking about the algorithms that operate in those structures. Different algorithms can vary in performance even if you're using the same data structure. For example, consider performing a binary search in a sorted array, which is logarithmic or O(lg(n)), vs sequential search in an unsorted array, which is O(n) or linear.
There's usually a trade-off when selecting an algorithm to operate on a specific data structure. (Using Big-O notation we get an idea of the asymptotic upper bound for the 'worst case' performance of an algorithm.) There're a few options, but none that will meet all the requirements at once, for the worst case at least. Think about it, if we had algorithms that could do everything in constant time, why would we need to have so many different ones? ;)
That being said, you can consider the average performance of some of these and you might be able to make a reasonable pick. For example, a hash table is O(1) for insert/delete/find on the average case, which could meet your requirement (depending on how flexible you're willing to be), but in the worst case it will be O(n). The behavior of other structures (e.g. Arrays) depend on whether they're sorted or not. For example, in an unsorted array, you can get O(1) for insertion, but for searches will take O(n).
You can use some domain information to make an educated guess regarding what your system will likely spend most of its time doing. For example, if you know the system will be performing searches most of the time, then you can make a tradeoff and choose an algorithm with a lower upper bound (e.g. O(lg(n)) instead of O(n)) on searches, even if insertion/deletion is not as good.
Whether something is 'sorted' or not will make sense depending on the data structure you choose. For example, a tree structure is not inherently 'sorted'; the 'sorting' is produced by the method used to traverse it (e.g. pre-order, in-order, post-order).
If the structure needs to quickly report the max/min values, it might be worth keeping a cached copy of the value in order to avoid searching for it. Again, this is a tradeoff of consuming additional memory to reduce the cost of a search.
You could do something like the following (pseudo-code):
void SomeClass::insert(int value) {
// add value into internal structure
this->_values.push_back(value);
// check cached copy
if(value > this->_max_value)
this->_max_value = value;
else if(value < this->_min_value)
this->_min_value = value;
}
Then you'd only need to return your cached copies when needed. Note that there's still a tradeoff here: You have to spend some time and logic keeping these cached copies up-to-date. In other words, check every point where something can be added and then updating these copies again at every point when they're deleted --which will incur a search for the max/min value from the elements that remain. The benefit of caching can quickly go away, or even become a detriment, if your system will spend most of the time adding and removing elements instead of searching. So, as mentioned previously, you should use your domain knowledge of the problem to make a best-guess and decide which tradeoffs are worth the effort.
