They are basically asking to implement a data structure, that adds, removes and find max in O(1). If we check running times for the best data structures for the task (https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times), the best known result is: O(1), O(1), O(log n).

Am I missing something?

UPDATE: sorry. I've incorrectly understood the task. I thought, max/min of keys should be computed.