Efficient priority queue with multiple keys?
<p>I have run into a problem which I am pretty certain somebody has allready encountered and solved, but I just can't find a solution. </p>

<p>I have a number of objects, each object has several keys. Say:</p>

<ul>
<li>(1, 2): A </li>
<li>(3, 3): B</li>
<li>(4, 4): C</li>
<li>(5, 1): D</li>
</ul>

<p>I need a "priority queue"-like data structure which lets me efficiently return objects by priority for each of the keys separately. For example, if I return them by the first key, I would get (A, B, C, D), and by the second key, I would get (D, A, B, C). However, I also need to be able to mix. For example, returning by the keys alternatively, starting with the first one, giving me (A, D, B, C). Obviously, popping an object by the first key should remove the second key.</p>

<p>A naive solution is resort the data when changing the lookup key, but it is too slow for my purposes. Another alternative is to use a heap and traverse the other heap for each object remove, but as far as I can tell that is also slow. Is there an algorithm for an efficient priority queue that lets me remove objects by multiple different keys?</p>

<p>If there is an implementation for python it would be really nice, but an algorithm would be a very good start. </p>