Eliminación de un elemento arbitrario de la cola de prioridad

Question

¿Cómo puedo eliminar un elemento arbitrario de una cola de prioridad? Supongamos que tengo una Prioridad para trabajos. Tengo un trabajo que quiero "cancelar", así que tengo que eliminarlo de la cola, ¿cómo puedo hacer eso?

ACTUALIZACIÓN

Para añadir a la respuesta, una pregunta relacionada: https://stackoverflow.com/a/9288081/292291

Answer 1

Supongo que está utilizando heapq. El documentation tiene esto que decir acerca de este problema, que parece bastante razonable:

Los desafíos restantes giran en torno a la búsqueda de una tarea pendiente y hacer cambios a su prioridad o eliminar por completo. Encontrar una tarea se puede hacer con un diccionario que apunta a una entrada en la cola.

Eliminar la entrada o cambiar su prioridad es más difícil porque rompería las invariantes de la estructura de pila. Por lo tanto, una posible solución es marcar la entrada existente como eliminada y agregar una nueva entrada con la prioridad revisada .

La documentación proporciona algo de código básico de ejemplo para mostrar cómo esto se puede hacer, que reproduzco aquí textualmente:

pq = []       # list of entries arranged in a heap 
entry_finder = {}    # mapping of tasks to entries 
REMOVED = '<removed-task>'  # placeholder for a removed task 
counter = itertools.count()  # unique sequence count 

def add_task(task, priority=0): 
    'Add a new task or update the priority of an existing task' 
    if task in entry_finder: 
     remove_task(task) 
    count = next(counter) 
    entry = [priority, count, task] 
    entry_finder[task] = entry 
    heappush(pq, entry) 

def remove_task(task): 
    'Mark an existing task as REMOVED. Raise KeyError if not found.' 
    entry = entry_finder.pop(task) 
    entry[-1] = REMOVED 

def pop_task(): 
    'Remove and return the lowest priority task. Raise KeyError if empty.' 
    while pq: 
     priority, count, task = heappop(pq) 
     if task is not REMOVED: 
      del entry_finder[task] 
      return task 
    raise KeyError('pop from an empty priority queue') 

Answer 2

de Python incorporada PriorityQueue no soporta la eliminación de cualquier elemento, excepto la parte superior. Si desea soporte para la eliminación de cualquier elemento, deberá implementar su propia cola (o buscar la implementación de otra persona).