Я пытаюсь реализовать приоритетную очередь в Python, используя heapq в качестве основы. Он отлично работает при непосредственном вводе значений, а затем их извлечении, но когда значения обновляются или удаляются между ними, значения начинают появляться в неправильном порядке.
Поскольку непосредственное изменение значений (я уже проверил это) не поддерживает инвариант кучи, вместо этого я очищаю исходный список значений, а затем вставляю обновленную версию. При извлечении значений из кучи, если извлекается пустой список, он будет извлекаться снова, пока не вернет правильное значение.
Я подумал, что инвариант каким-то образом был нарушен, несмотря на мои усилия, поэтому я использовал heapq.nsmallest(len(heap), heap) для проверки порядка значений. К моему удивлению, он всегда возвращал правильный порядок. Тем не менее, при удалении значений с помощью heapq.heappop(heap) они не возвращались в таком порядке. Как это возможно? Мой код ниже:
import heapq
class IndexedPriorityQueue:
def __init__(self, start: list | tuple):
self.added = 0
self.heap = []
self.key_values = {}
for index, item in enumerate(start):
self._add(item[0], index, item[1])
def add(self, item: str, priority: int):
if item in self.key_values:
return False
self._add(item, self.added, priority)
self.added += 1
def _add(self, item: str, index: int, priority: int):
next = [-priority, index, item]
self.key_values[item] = next
heapq.heappush(self.heap, next)
def pop(self):
if not self.heap:
return
value = heapq.heappop(self.heap)
while not value:
value = heapq.heappop(self.heap)
return value[2]
def remove(self, item: str):
if self.key_values[item] is self.heap[0]:
heapq.heappop(self.heap)
else:
self.key_values[item].pop()
self.key_values[item].pop()
self.key_values[item].pop()
del self.key_values[item]
def update(self, item: str, new_priority: int):
if self.key_values[item] is self.heap[0]:
new = [-new_priority, self.key_values[item][1], item]
heapq.heapreplace(self.heap, new)
self.key_values[item] = new
else:
self.key_values[item].pop()
index = self.key_values[item].pop()
self.key_values[item].pop()
self._add(item, index, new_priority)
ipq = IndexedPriorityQueue((["First", 1], ["Third", 10], ["Second", 0], ["Fifth", 7], ["Fourth", 6], ["None", 9999]))
print("Actual: ", heapq.nsmallest(len(ipq.heap), ipq.heap))
return_list = []
while (next_val := ipq.pop()) is not None:
return_list.append(next_val)
print("Returned: ", return_list)
ipq = IndexedPriorityQueue((["First", 1], ["Third", 10], ["Second", 0], ["Fifth", 7], ["Fourth", 6], ["None", 9999]))
ipq.add("Sixth", 0)
ipq.update("First", 9999)
ipq.remove("None")
ipq.update("Second", 999)
ipq.update("Fourth", 8)
print("Actual: ", heapq.nsmallest(len(ipq.heap), ipq.heap))
return_list = []
while (next_val := ipq.pop()) is not None:
return_list.append(next_val)
print("Returned: ", return_list)
Напечатанные значения:
Actual: [[-9999, 5, 'None'], [-10, 1, 'Third'], [-7, 3, 'Fifth'], [-6, 4, 'Fourth'], [-1, 0, 'First'], [0, 2, 'Second']]
Returned: ['None', 'Third', 'Fifth', 'Fourth', 'First', 'Second']
Actual: [[], [], [], [-9999, 0, 'First'], [-999, 2, 'Second'], [-10, 1, 'Third'], [-8, 4, 'Fourth'], [-7, 3, 'Fifth'], [0, 0, 'Sixth']]
Returned: ['First', 'Third', 'Second', 'Fourth', 'Fifth', 'Sixth']
Пустые списки также не все всплывают в начале.
heapq.nsmallest
не предполагает, что ввод представляет собой кучу; он использует отдельную кучу для поиска n наименьших элементов в любой итерации. Вы не можете использовать его для проверки того, имеет ли список свойство кучи, потому что он будет выдавать выходные данные в правильном порядке независимо от их порядка во входных данных.
@TimRoberts Я делал это намеренно, потому что было бы более затратно с вычислительной точки зрения каждый раз использовать все это целиком. Я полагал, что не имеет значения, если пустые списки были неуместны, поскольку они отбрасывались в тот момент, когда их выталкивали.
Если я заменю ваш remove
на это:
def remove(self, item: str):
self.heap.remove(self.key_values[item])
del self.key_values[item]
heapq.heapify(self.heap)
тогда порядок, кажется, поддерживается.
Да, но при этом вы теряете благо эффективности кучи. Это делает операцию удаления O(n).
Технически это работает, но требует обращения ко всей куче за линейное время каждый раз, когда что-либо изменяется или удаляется (кроме того, что находится сверху), чего я бы предпочел избежать.
Конечно, но какая альтернатива есть? Модуль heapq
не настроен для обработки операции удаления за пределами подсказки. Вы пытаетесь сделать что-то, для чего довольно простой модуль heapq
не предназначен. Итак, вы делаете свое коверканье, а затем позволяете heapq
освежиться. Куча почти отсортирована, поэтому heapify
должен работать быстро.
Очищая элементы (списки), находящиеся в куче, можно нарушить свойство кучи. Такой пустой элемент становится меньше, чем его родитель, что нарушает свойство minheap (heapq), и это негативно повлияет на поведение будущих операций с кучей, что приведет к большей несогласованности.
Вы можете решить эту проблему, не очищая элемент, который необходимо удалить/заменить, а удалив только последний элемент из этого элемента, чтобы он уменьшил его длину до 2. Эти два оставшихся значения по-прежнему позволят поддерживать свойство кучи. , в то время как вы также можете определить (по уменьшенной длине), что элемент действительно удален.
Вот что обновить:
def remove(self, item: str):
if self.key_values[item] is self.heap[0]:
heapq.heappop(self.heap)
else:
# Perform only one pop so to leave 2 members in the list
self.key_values[item].pop()
del self.key_values[item]
def update(self, item: str, new_priority: int):
if self.key_values[item] is self.heap[0]:
new = [-new_priority, self.key_values[item][1], item]
heapq.heapreplace(self.heap, new)
self.key_values[item] = new
else:
self.key_values[item].pop() # Only pop the last member
index = self.key_values[item][-1] # Don't pop this one -- just read
self._add(item, index, new_priority)
def pop(self):
if not self.heap:
return
value = heapq.heappop(self.heap)
while len(value) < 3: # Changed test for delete-mark
if not self.heap: # Protection needed!
return
value = heapq.heappop(self.heap)
return value[2]
Теперь вывод вашего скрипта будет заканчиваться:
Returned: ['First', 'Second', 'Third', 'Fourth', 'Fifth', 'Sixth']
Пустые элементы возникают из-за того, что вы изменяете объекты списка напрямую (в
remove
) без уведомления heapq. Вы нарушаете инвариант кучи, потому что эти элементы теперь не по порядку. Возможно, вы можете просто удалить эти элементы, а затем использоватьheapify
, чтобы восстановить порядок.