Python heapq not being pushed in right order?
python
Solution
The `heapq` 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)
Problem
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