Python heapq 没有按正确的顺序推送

工具.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 

打印出来

(3, '2UA') 
(4, '6FD6') 
(6, 'DLB66A')          <---out of place 
(4, 'J97K') 
(7, 'GFQMRZZ')         <----out of place 
(6, 'SRU5T4') 
(7, 'BP4PGKH') 
(7, 'CBUJWQO') 
(7, '5KNNY1P') 

为什么这两个不合适，如何解决？

当我在 for i in rdy.getHeap():
中添加 print rdy.pop() 时 当我插入 9 个时它只弹出 5 个

请您参考如下方法:

heapq 函数不会让您的列表排序，但只能保证堆属性得到维护:

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

因此，heap[0]总是最小的项目。

当你想按优先顺序遍历项目时，你不能简单地遍历堆，而是需要 pop()项目关闭，直到队列为空。 heappop()将获取第一项，然后重新组织列表以实现堆不变性。

另请参阅:http://en.wikipedia.org/wiki/Heap_(data_structure)