Usuwanie dowolnego elementu z kolejki priorytetowej

Question

Jak usunąć dowolny element z kolejki priorytetowej. Załóżmy, że mam PriorityQueue dla zadań. Mam pracę, którą chcę "anulować", więc muszę ją usunąć z kolejki, jak mogę to zrobić?

UPDATE

Aby dodać do odpowiedzi, powiązanego pytanie: https://stackoverflow.com/a/9288081/292291

Answer 1

Zakładam, że używasz heapq. documentation ma do powiedzenia na temat tego problemu, co wydaje się całkiem rozsądne:

Pozostałe wyzwania obróconego wokół znalezienie oczekujące zadania i wprowadzania zmian do swojego priorytetu lub usunięcie go w całości. Znalezienie zadania można wykonać za pomocą słownika wskazującego pozycję w kolejce.

Usunięcie wpisu lub zmiana jego priorytetu jest trudniejsza, ponieważ zerwałoby niezmienniki struktury sterty. Zatem możliwe rozwiązanie polega na oznaczeniu istniejącego wpisu jako usunięty i dodaniu nowego wpisu ze zmienionym priorytetem .

Dokumentacja zawiera podstawowe przykładowy kod, aby pokazać w jaki sposób można to zrobić, co ja tu rozmnażać verbatim:

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

Python wbudowanej PriorityQueue nie umożliwia usunięcie dowolnego elementu z wyjątkiem górnej. Jeśli chcesz mieć możliwość usunięcia dowolnego elementu, musisz zaimplementować własną kolejkę (lub znaleźć implementację innej osoby).