Python heapq not being pushed in right order?
Question: 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) for x in range(random.randint(2,8)))
    
    def pqfunc(item):
        return len(str(item))
    
    rdy = Util.PriorityQueueFunction(pqfunc)
    for i in range(1,10):
        rdy.push(str_gen())
    
    for i in rdy.getHeap():
        print i
    

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 are those two out of place and how to fix?

and when I add print `rdy.pop()` inside `for i in rdy.getHeap():`  
it only pops 5 of them when i pushed in 9


Answer: The [`heapq`](http://docs.python.org/2/library/heapq.html) functions do not
keep your list _sorted_ , but only guarantee that the _heap property_ is
maintained:

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

Consequently, `heap[0]` is always the smallest item.

When you want to iterate over the items in order of priority, you cannot
simply iterate over the heap but need to `pop()` items off until the queue is
empty. `heappop()` will take the first item, then reorganize the list to
fulfil the heap invariant.

See also: <http://en.wikipedia.org/wiki/Heap_(data_structure)>

