Python heapq not being pushed in right order? -

util.py

import heapq class priorityqueue:     def __init__(self):         self.heap=[]      def push(self,item,priority):         pair = (priority,item)         heapq.heappush(self.heap,pair)      def pop(self):         (priority,item) = heapq.heappop(self.heap)         return item      def getheap(self):         return self.heap  class priorityqueuewithfunction(priorityqueue):     def __init__ (self,priorityfunction):         self.priorityfunction = priorityfunction         priorityqueue.__init__(self)      def push(self,item):         priorityqueue.push(self, item, self.priorityfunction(item)) 

pqtest.py

import os,sys lib_path = os.path.abspath('../../lib/here') sys.path.append(lib_path)  import util import string import random  def str_gen():     return ''.join(random.choice(string.ascii_uppercase + string.digits) x in range(random.randint(2,8)))  def pqfunc(item):     return len(str(item))  rdy = util.priorityqueuefunction(pqfunc) in range(1,10):     rdy.push(str_gen())  in rdy.getheap():     print 

it printed

(3, '2ua') (4, '6fd6') (6, 'dlb66a')          <---out of place (4, 'j97k') (7, 'gfqmrzz')         <----out of place (6, 'sru5t4') (7, 'bp4pgkh') (7, 'cbujwqo') (7, '5knny1p') 

why 2 out of place , how fix?

and when add print rdy.pop() inside for in rdy.getheap():
pops 5 of them when pushed in 9

the heapq functions not keep list sorted, guarantee heap property maintained:

• heap[k] <= heap[2*k+1]
• heap[k] <= heap[2*k+2]

consequently, heap[0] smallest item.

when want iterate on items in order of priority, cannot iterate on heap need pop() items off until queue empty. heappop() take first item, reorganize list fulfil heap invariant.

see also: http://en.wikipedia.org/wiki/heap_(data_structure)