You will need two priority queues.