Data structure with constant 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.