Xóa một mục tùy ý khỏi hàng đợi ưu tiên

Question

Làm cách nào để xóa một mục tùy ý khỏi hàng đợi ưu tiên. Giả sử tôi có một PriorityQueue cho công việc. Tôi có một công việc tôi muốn "hủy bỏ" vì vậy tôi cần phải loại bỏ nó khỏi hàng đợi, làm thế nào tôi có thể làm điều đó?

CẬP NHẬT

Để thêm vào câu trả lời, một câu hỏi liên quan: https://stackoverflow.com/a/9288081/292291

Answer 1

Tôi giả sử bạn đang sử dụng heapq. Các documentation có này để nói về vấn đề này, trong đó có vẻ khá hợp lý:

Những thách thức còn lại xoay quanh việc tìm kiếm một nhiệm vụ cấp phát và làm thay đổi ưu tiên của nó hoặc loại bỏ nó hoàn toàn. Tìm một nhiệm vụ có thể được thực hiện bằng một từ điển trỏ đến một mục trong hàng đợi.

Xóa mục nhập hoặc thay đổi mức độ ưu tiên của nó khó hơn vì nó sẽ phá vỡ các bất biến cấu trúc vùng heap. Vì vậy, một giải pháp có thể là đánh dấu mục nhập hiện có là đã bị xóa và thêm mục nhập mới với mức ưu tiên được sửa đổi là .

Các tài liệu cung cấp một số mã ví dụ cơ bản để hiển thị như thế nào điều này có thể được thực hiện, mà tôi sinh sản ở đây nguyên văn:

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 tích hợp trong PriorityQueue không hỗ trợ loại bỏ bất kỳ mục nào ngoại trừ đỉnh. Nếu bạn muốn hỗ trợ loại bỏ bất kỳ mục nào, bạn sẽ cần phải triển khai hàng đợi của riêng bạn (hoặc tìm cách triển khai của người khác).