Переопределение приоритетной очереди (эффективный способ)

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(.), когда repriorizating очереди приоритета ? Я здесь готов торговать памятью за скорость, но ее можно реализовать в чистом Python (очевидно, с гораздо более лучшими таймингами, чем моя наивная реализация).

Update:
Для того, чтобы позволить вам понять больше о конкретном случае, позволяет предположить, что никакие элементы не будут добавлены в очередь после начальной (партии) отталкивает, а затем каждый выборки (поп) из очереди будет генерировать количество repriorizations примерно как такой схеме:

• 0 * n, очень редко
• 0,05 * n, обычно
• n, очень редко

n - текущее число items в очереди. Таким образом, в любом раунде существует более или менее относительное количество предметов для переориентации. Поэтому я надеюсь, что может существовать структура данных, которая сможет использовать этот шаблон и, следовательно, превосходить затраты на выполнение обязательных heapify(.) в каждом раунде (чтобы удовлетворить инварианту кучи).

Update 2:
До сих пор, кажется, что heapify(.) подход является достаточно эффективным (условно говоря) на самом деле. Все альтернативы, которые я смог выяснить, должны использовать heappush(.), и это кажется более дорогим, что я изначально ожидал. (В любом случае, если состояние проблемы остается таким, я вынужден найти лучшее решение из области python).

Answer 1

Поскольку новая функция приоритизации не может иметь никакого отношения к предыдущей, вы должны оплатить стоимость, чтобы получить новый заказ (и это минимальное значение O (n), чтобы найти минимальный элемент в новом порядке). Если у вас есть небольшое фиксированное количество функций приоритизации и часто переключаться между ними, вы можете выиграть от сохранения отдельной кучи для каждой функции (хотя и не с heapq, поскольку она не поддерживает дешевое размещение и удаление и объект из середина кучи).