Python имеет модуль heapq, который реализует структуру данных кучи и поддерживает некоторые основные операции (push, pop).
Как удалить i-й элемент из кучи в O (log n)? Возможно ли это с помощью heapq или мне нужно использовать другой модуль?
Обратите внимание: в нижней части документации есть пример: http://docs.python.org/library/heapq.html которые предполагают возможный подход - это не то, что я хочу. Я хочу, чтобы элемент удалялся, а не просто отмечался как удаленный.
Вы можете легко удалить i-й элемент из кучи:
h[i] = h[-1]
h.pop()
heapq.heapify(h)
Просто замените элемент, который вы хотите удалить с помощью последнего элемента, и удалите последний элемент, а затем повторно наведите кучу. Это O (n), если вы хотите, чтобы вы могли сделать то же самое в O (log (n)), но вам нужно будет вызвать пару внутренних функций heapify или лучше, если только larsmans укажет, что просто скопируйте источник _siftup/_siftdown из heapq.py в свой собственный код:
h[i] = h[-1]
h.pop()
if i < len(h):
heapq._siftup(h, i)
heapq._siftdown(h, 0, i)
Обратите внимание, что в каждом случае вы не можете просто сделать h[i] = h.pop(), поскольку это не сработает, если i ссылается на последний элемент. Если вы делаете особый случай удалением последнего элемента, вы можете комбинировать перезапись и поп.
Обратите внимание, что в зависимости от типичного размера вашей кучи вы можете обнаружить, что просто вызов heapify, тогда как теоретически менее эффективный может быть быстрее, чем повторное использование _siftup/_siftdown: немного интроспекции покажет, что heapify, вероятно, реализован в C, но реализация внутренних функций C не раскрывается. Если для вас важна производительность, подумайте о том, чтобы выполнить некоторые временные тесты по типичным данным, чтобы увидеть, что лучше. Если у вас нет действительно массивных куч, big-O не может быть самым важным фактором.
Изменить: кто-то попытался отредактировать этот ответ, чтобы удалить вызов _siftdown с комментарием, который:
_siftdown не требуется. Новый h [i] гарантированно будет самым маленьким из старых h [i] детей, который все еще больше, чем старый h [i] родитель (новый h [i] родительский элемент). _siftdown будет no-op. Мне нужно отредактировать, так как я у меня недостаточно комментариев, чтобы добавить комментарий еще.
То, что они пропустили в этом комментарии, состоит в том, что h[-1] не может быть дочерним элементом h[i] вообще. Новое значение, вставленное в h[i], может происходить из совершенно другой ветки кучи, поэтому ее необходимо просеять в любом направлении.
Также в комментарии спрашивается, почему не просто использовать sort() для восстановления кучи: вызов _siftup и _siftdown - это операции O (log n), вызывающие heapify - O (n). Вызов sort() - это операция O (n log n). Вполне возможно, что сортировка вызова будет достаточно быстрой, но для больших кучек это лишние накладные расходы.
Отредактировано, чтобы избежать проблемы, отмеченной @Seth Bruder. Когда i ссылается на конечный элемент, вызов _siftup() завершился неудачно, но в этом случае выскальзывание элемента с конца кучи не нарушает инвариант кучи.
(a) Подумайте, почему вы не хотите ленивого удаления. Это правильное решение во многих случаях.
(b) Куча - это список. Вы можете удалить элемент по индексу, как и любой другой список, но тогда вам нужно будет повторно его переустановить, потому что он больше не будет удовлетворять инварианту кучи.