Insert and get max from structure in constant time
There is no such data structure. For example, if there were, sorting would be worst-case linear time:  add all N elements in O(N) time, then remove the largest element remaining N times, again in total O(N) time.
I need a data structure to store positive (not necessarily integer) values. It must support the following two operations in sublinear time:

Add an element.
Remove the largest element.

Also, the largest key may scale as N^2, N being the number of elements. In principle, having O(N^2) space requirement wouldn't be a big problem, but if a more efficient option exists in terms of store, it would work better.
I am working in Python, so if such a data structure exists, it would be of help to have an implementation in this language.