Как реализовать приоритетную очередь?

Задача написать программу читающую из файла описания операций с очередью и выводящую в другой файл результат выполнения всех операций 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

"ошибка времени исполнения" заменяется на "неверный ответ" на том же тесте