そうか、ちょっと勘違いしてました。並行にキューに入れたときにどの順番で突っ込まれたかは重要ではないから、優先度の高いアイテムはプライオリティに基づいて（たとえばバブルソートの要領で末尾から舐めて）適切な位置に挿入すればいいんじゃないかと思ってましたが、同じスレッドから順番にキューに入れた場合は順番が保証されていないと困る場合もあるから、キューに入っているアイテムの順番は入れ替えることはできなですね。なので、優先度の高いアイテムより前にあるアイテムの優先度を高めるしかないと。