Задача написать программу читающую из файла описания операций с очередью и выводящую в другой файл результат выполнения всех операций extract-min. Если перед очередной операцией extract-min очередь пуста, выводит вместо числа звездочку.
Пример:
priorityqueue.in priorityqueue.out
push 3 2
push 4 1
push 2 3
extract-min *
decrease-key 2 1
extract-min
extract-min
extract-min
Я написал реализацию с использованием списка, куда каждый элемента добавлял с бинарным поиском, чтобы массив был всегда отсортирован
import bisect, sys
sys.stdout = open("priorityqueue.out", "w")
queue = []
operations = open("priorityqueue.in").read().strip().split("\n")
for op in operations:
op_parsed = op.split()
if op_parsed[0] == "push":
bisect.insort(queue, int(op_parsed[1]))
elif op_parsed[0] == "extract-min":
try:
print(queue[0])
del queue[0]
except:
print("*")
else:
del queue[int(op_parsed[1]) - 1]
bisect.insort(queue, int(op_parsed[2]))
Но проблема в том, что на некотором тесте была "ошибка времени исполнения". Как я выяснил эмпирическим путем на строчке
del queue[int(op_parsed[1]) - 1] кидается исключение и скорее всего это было
IndexError, но из-за чего оно кидается я понять не могу.
До этого я написал реализацию с использованием
heapq у которой тоже была "ошибка времени исполнения" на том же месте
import heapq, sys
sys.stdout = open("priorityqueue.out", "w")
queue = []
operations = open("priorityqueue.in").read().strip().split("\n")
for op in operations:
op_parsed = op.split()
if op_parsed[0] == "push":
heapq.heappush(queue, int(op_parsed[1]))
elif op_parsed[0] == "extract-min":
try:
print(heapq.heappop(queue))
except IndexError:
print("*")
else:
queue[int(op_parsed[1]) - 1] = queue[-1]
queue.pop()
heapq.heappush(queue, int(op_parsed[2]))
P.S. При попытке добавления блока
try:
...
except:
pass
"ошибка времени исполнения" заменяется на "неверный ответ" на том же тесте
