heapq сравнивает кортежи по полям. Поэтому запись (приоритет, задача) при равных приоритетах либо сравнит сами задачи, либо упадёт, если объекты несравнимы. Надёжная форма: (приоритет, номер, задача), где номер выдаёт itertools.count(). Он сохраняет порядок добавления и не допускает сравнения задач.Искать и удалять произвольную запись по идентификатору куча эффективно не умеет. Для отмены и смены приоритета можно хранить активные записи в словаре: старую помечать удалённой, новую добавлять в кучу, а помеченные пропускать при извлечении. Лень здесь вполне питонична.
У этой схемы очереди есть цена: устаревшие записи занимают память, пока не доберутся до вершины. Если обновлений много, а извлечений мало, кучу стоит периодически пересобирать из активных записей.