I don't see how both Insert and ExtractMax can be O(1). Obviously Insert can be O(1) if you just append new elements to the end of a vector, but then ExtractMax would be O(n) since you'd have to search the entire vector. You may be able to take advantage of special properties of your key, but in general you won't be able to get both operations below sqrt(log n) or maybe log log n.