Fastest data structure for a priority queue

You have Float64 times and yet they collide?

In any case, for a SortedMultiDict you’d just iterate over them and they’d come in order of the time/key and if there are same key they’d come in order of when they were inserted. I don’t see the issue.

The “limitations” you mention are not really limitations. You agree that your keys are all Float64 so they’re “the same type as one another” and the values can all be Any if you don’t have a common thing.