3

实用程序.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')

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

rdy.pop()当我在里面 添加打印for i in rdy.getHeap():
时，当我推入 9 时，它只会弹出 5 个

4

2 回答 2

13

这些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)

于 2013-08-08T04:58:01.013 回答
1

如果你想要一个按顺序排列的列表，你可以使用 heapq 的 nsmallest 和 nlargest 函数。

heapq.nsmallest(len(my_heap), my_heap) - 从最小到最大的列表

heapq.nlargest(len(my_heap), my_heap) - 从大到小列出

于 2016-01-19T14:13:21.473 回答