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

Question

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

Answer 1

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)