title: Python: Priority queue does'nt keep order on same priority elements
body: <p>I'm using python's <code>Queue.PriorityQueue</code>, and ran into the following problem: when inserting several elements to the queue which have <strong>the same priority</strong>, I would expect the queue to serve them in the order of insertion (FIFO). For some reason this is not the case:</p>
  
  <pre><code>&gt;&gt;&gt; from Queue import PriorityQueue
  &gt;&gt;&gt;
  &gt;&gt;&gt; j1 = (1, 'job1')
  &gt;&gt;&gt; j2 = (1, 'job2')
  &gt;&gt;&gt; j3 = (1, 'job3')
  &gt;&gt;&gt; j4 = (1, 'job4')
  &gt;&gt;&gt; 
  &gt;&gt;&gt; q = PriorityQueue()
  &gt;&gt;&gt; q.put(j1)
  &gt;&gt;&gt; q.put(j2)
  &gt;&gt;&gt; q.put(j3)
  &gt;&gt;&gt; q.put(j4)
  &gt;&gt;&gt; q.queue
  [(1, 'job1'), (1, 'job2'), (1, 'job3'), (1, 'job4')]
  &gt;&gt;&gt; q.get()
  (1, 'job1')
  &gt;&gt;&gt; q.queue
  [(1, 'job2'), (1, 'job4'), (1, 'job3')]
  </code></pre>
  
  <p>As can be seen from the example, the order has been mixed after one <code>get()</code>.
  What's the reason? how to overcome (keep the order of same prio elements)?</p>
  
  <p><strong>EDIT</strong>:</p>
  
  <p>I was asked to add an example that shows that <code>q.get()</code> actually mess things up with the FIFO ordering, so here's an elaborate example:</p>
  
  <pre><code>class Job(object):
      def __init__(self, type_, **data):
          self.type_ = type_
          self.priority = 0 if self.type_ == 'QUIT' else 1
          self.data = data
  
      def __cmp__(self, other):
          return cmp(self.priority, other.priority)
  
      def __repr__(self):
          return 'Job("' + self.type_ + '", data=' + repr(self.data) + ')' 
  
  q = PriorityQueue()
  q.put(Job('Build'))
  q.put(Job('Clean'))
  q.put(Job('QUIT'))
  q.put(Job('Create'))
  q.put(Job('Build'))
  q.put(Job('Clean'))
  </code></pre>
  
  <p>Now I'll dequeue the elements one by one. The expected result: QUIT goes out first, and then the rest, FIFO ordered: Build, Clean, Create, Build, Clean:</p>
  
  <pre><code>&gt;&gt;&gt; q.get()
  Job("QUIT", data={})
  &gt;&gt;&gt; q.get()
  Job("Build", data={})
  &gt;&gt;&gt; q.get()
  Job("Clean", data={})
  &gt;&gt;&gt; q.get()
  Job("Build", data={}) # &lt;&lt;---
  &gt;&gt;&gt; q.get()
  Job("Clean", data={})
  &gt;&gt;&gt; q.get()
  Job("Create", data={})
  </code></pre>