You could do (category, random priority) and then do lexicographic comparison. That way higher categories always outrank lower categories.

But depending on what you need, you might also just do (random priority + weight * category) or so. Or you just keep separate reservoirs for high importance items and for everything else.