重新确定优先级队列的优先级(有效方式)

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,非常少见
• n通常为0.05*
• n, 很少

其中n是items队列中的当前数量.因此,在任何一轮中,或多或少只有相对较少的物品要重新制作.所以我希望可能存在一个能够利用这种模式的数据结构,因此heapify(.)在每一轮中都能胜过强制执行的成本(为了满足堆不变量).

更新2:
到目前为止,这种heapify(.)方法似乎确实非常有效(相对而言).我能够找到的所有替代品都需要利用,heappush(.)而且它似乎比我原先预期的更昂贵.(无论如何,如果问题的状态仍然如此,我不得不在这个python领域找到更好的解决方案).

Answer 1

由于新的优先级函数可能与前一个函数没有任何关系，因此您必须付出成本才能获得新的排序（并且至少需要 O(n) 才能找到新排序中的最小元素）。如果你有少量固定数量的优先级函数并且在它们之间频繁切换，那么你可以从为每个函数保留一个单独的堆中受益（尽管不是使用 heapq，因为它不支持廉价地定位和删除对象。堆的中间）。