We need more than just a RB tree/skip list because we need to update
the priority of elements *without knowing their priority*. This
implies that we also need a hashmap.