高效地重新排序优先队列

Question

我在寻找一种更高效的方法来重新调整优先队列中的项目优先级。我现在的优先队列实现是基于 heapq 的，比较简单。相关的部分如下：

from heapq import heapify, heappop

class pq(object):
    def __init__(self, init= None):
        self.inner, self.item_f= [], {}
        if not None is init:
            self.inner= [[priority, item] for item, priority in enumerate(init)]
            heapify(self.inner)
            self.item_f= {pi[1]: pi for pi in self.inner}

    def top_one(self):
        if not len(self.inner): return None
        priority, item= heappop(self.inner)
        del self.item_f[item]
        return item, priority

    def re_prioritize(self, items, prioritizer= lambda x: x+ 1):
        for item in items:
            if not item in self.item_f: continue
            entry= self.item_f[item]
            entry[0]= prioritizer(entry[0])
        heapify(self.inner)

这里有一个简单的协程，用来展示我实际应用中重新调整优先级的特点。

def fecther(priorities, prioritizer= lambda x: x+ 1):
    q= pq(priorities)
    for k in xrange(len(priorities)+ 1):
        items= (yield k, q.top_one())
        if not None is items:
            q.re_prioritize(items, prioritizer)

经过测试

if __name__ == '__main__':
    def gen_tst(n= 3):
        priorities= range(n)
        priorities.reverse()
        priorities= priorities+ range(n)
        def tst():
            result, f= range(2* n), fecther(priorities)
            k, item_t= f.next()
            while not None is item_t:
                result[k]= item_t[0]
                k, item_t= f.send(range(item_t[0]))
            return result
        return tst

得到了：

In []: gen_tst()()
Out[]: [2, 3, 4, 5, 1, 0]
In []: t= gen_tst(123)
In []: %timeit t()
10 loops, best of 3: 26 ms per loop

现在，我的问题是，有没有一种数据结构可以在重新调整优先队列时避免调用 heapify(.)？我愿意为了速度而牺牲一些内存，但它应该可以用纯 Python 实现（显然，性能要比我简单的实现好得多）。

更新:
为了让你更好地理解具体情况，假设在最初（批量）推送后，不再向队列中添加任何项目，然后每次从队列中取出（弹出）时，重新调整优先级的次数大致如下：

0* n，非常少见
0.05* n，通常情况
n，非常少见

其中 n 是队列中当前的 items 数量。因此，在每一轮中，实际上只有相对较少的项目需要重新调整优先级。所以我希望能有一种数据结构能够利用这个模式，从而降低每轮都必须进行 heapify(.) 的成本（以满足堆的性质）。

更新 2:
到目前为止，似乎 heapify(.) 的方法确实相对高效。我能想到的所有替代方案都需要使用 heappush(.)，而且似乎比我最初预期的要昂贵得多。（无论如何，如果问题的状态保持不变，我就不得不在 python 的范围之外寻找更好的解决方案）。

性能优化数据结构内存管理协程算法效率优先队列优先级调整堆的性质

高效地重新排序优先队列

1 个回答

撰写回答