In the vast majority of cases, premature optimisation will cause you pain for little to no benefit. Unless you know for sure that it is a problem, don't worry about it.
It's more important that your game works correctly in the first instance, so using java.util.PriorityQueue is probably the best and easiest way to go for now.
If you get to the point that you have profiled your game and PriorityQueue is showing as a bottleneck, then you can worry about writing a drop-in replacement.
However, be aware of this
. It caused me much puzzlement.
As an aside, wouldn't it be better to process events in the order that they happened? For example, if you receive the movement updates that show some car has piled into a wall, and the death event for the now-flaming wreck in the same frame, you might end up drawing the explosion in the wrong place if you process the death event before the movement updates. Similarly, if death events have a higher priority than player join events, you might end up with the situation where a non-existent player dies!