Frage Entfernen eines beliebigen Elements aus der Prioritätswarteschlange


Wie kann ich ein beliebiges Element aus einer Prioritätswarteschlange entfernen? Angenommen, ich habe eine Prioritätsqueue für Jobs. Ich habe einen Job, den ich abbrechen möchte, also muss ich ihn aus der Warteschlange entfernen. Wie kann ich das tun?

AKTUALISIEREN

Um der Antwort eine verwandte Frage hinzuzufügen: https://stackoverflow.com/a/9288081/292291


6
2018-02-15 04:11


Ursprung


Antworten:


Ich nehme an, du benutzt es heapq. Das Dokumentation hat zu diesem Problem etwas zu sagen, was ganz vernünftig erscheint:

Die verbleibenden Herausforderungen drehen sich darum, eine ausstehende Aufgabe zu finden und   Änderungen an seiner Priorität vornehmen oder sie vollständig entfernen. Eine Aufgabe finden   kann mit einem Wörterbuch gemacht werden, das auf einen Eintrag in der Warteschlange zeigt.

Das Entfernen des Eintrags oder das Ändern seiner Priorität ist schwieriger, weil   es würde die Invarianten der Heap-Struktur aufbrechen. Also, eine mögliche Lösung   Markieren Sie den bestehenden Eintrag als entfernt und fügen Sie einen neuen Eintrag mit hinzu   überarbeitete Priorität.

Die Dokumentation bietet einige grundlegende Beispiel-Code, um zu zeigen, wie dies getan werden kann, die ich hier wörtlich reproduzieren:

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')

5
2018-02-15 04:15



Python ist eingebaut PriorityQueue unterstützt nicht das Entfernen von Elementen außer oben. Wenn Sie Unterstützung für das Entfernen von Elementen benötigen, müssen Sie eine eigene Warteschlange implementieren (oder die Implementierung einer anderen Person suchen).


4
2018-02-15 04:14