title: PriorityQueue is very slow
body: <p>I'm implementing a mathematical function, and I need to have a priority queue. I use this code found on this page:</p>
  
  <pre><code>class MyPriorityQueue(PriorityQueue):
  
      def __init__(self):
          PriorityQueue.__init__(self)
          self.counter = 0
  
      def put(self, item, priority):
          PriorityQueue.put(self, (priority, self.counter, item))
          self.counter += 1
  
      def get(self, *args, **kwargs):
  
          if self.counter == 0:
              return None
  
          _, _, item = PriorityQueue.get(self, *args, **kwargs)
          self.counter -= 1
          return item
  
      def empty(self):
  
          if self.counter == 0:
              return True
  
          return False
  </code></pre>
  
  <p>It is known that python is slow, but seeing the results I realized that the dequeue consumes 28% of total execution time. Anyone got any suggestions?</p>
  
  <pre><code>Line #      Hits         Time  Per Hit   % Time  Line Contents
  ==============================================================
      34                                               @profile
      35                                               def solution(self):
      36                                           
      37         1           11     11.0      0.0          root = Node()
      38         1            2      2.0      0.0          root.capacity = self.K - root.size
      39         1           65     65.0      0.0          root.estimated = self.bound(root.level, root.size, root.value)
      40         1            4      4.0      0.0          root.copyList(None)
      41         1           37     37.0      0.0          self.queue.put(root, -0)
      42                                           
      43     99439       389936      3.9      2.3          while not self.queue.empty():
      44                                           
      45     99438      4666742     46.9     28.0              node = self.queue.get()
      46                                           
      47     99438       272335      2.7      1.6              if node.estimated &gt; self.maxValue:
      48                                           
  </code></pre>
  
  <p><strong>UPDATE:</strong></p>
  
  <p>Using heapq decreased almost half</p>
  
  <pre><code>Line #      Hits         Time  Per Hit   % Time  Line Contents
  ==============================================================
      67                                               @profile
      68                                               def solution(self):
      69                                           
      70         1           13     13.0      0.0          root = Node(0, 0, 0)
      71         1            2      2.0      0.0          root.capacity = self.K - root.size
      72         1           70     70.0      0.0          root.estimated = self.bound(root.level, root.size, root.value)
      73         1            5      5.0      0.0          root.copyList(None)
      74         1            5      5.0      0.0          heappush(self.queue, (-0, root))
      75                                           
      76     99439       171957      1.7      1.5          while self.queue:
      77                                           
      78     99438      2488221     25.0     21.7              node = heappop(self.queue)[1]
      79                                           
      80     99438       227451      2.3      2.0              if node.estimated &gt; self.maxValue:
  </code></pre>
  
  <p>Is there any way to optimize this loop?</p>
  
  <pre><code> while k &lt; self.numItems:
              estimated += self.items[k].value
              totalSize += self.items[k].weight
              k += 1
  </code></pre>