Удаление элемента из приоритетной очереди

Question

В Python модуль heapq предоставляет очередь с приоритетами.

Он имеет методы для вставки и извлечения элементов.

Как удалить элемент, которыйВы вставили не самый низкий приоритет из очереди?

(Альтернативные рецепты для этого с использованием альтернативных других коллекций тоже приветствуются)

Answer 1

Модуль heapq использует стандартные списки Python в качестве базовой структуры данных, поэтому после этого вы можете просто снова использовать стандартные методы list remove() и heapify(). Обратите внимание, что для этого потребуется линейное время.

# Create example data and heapify
a = range(10)
a.reverse()
heapq.heapify(a)
print a

# remove an element and heapify again
a.remove(5)
heapq.heapify(a)
print a

Вы можете улучшить производительность кучи еще раз, используя недокументированную функцию heapify._siftup(), но весь процесс все равно будет O (n), поскольку list.remove() - это O (n).

Answer 2

Если вы знаете местоположение элемента, который хотите удалить, вы можете сделать следующее:

a[k] = a.pop()
heapq.heapify(a)

Первый шаг теперь O (1), а второй может быть сделан O (войти (N)) с использованием недокументированных данных.Конечно, это все еще O (N), чтобы найти k, если у вас его еще нет.

Answer 3

Эта функция журнала (N) работает для меня:

def heapq_remove(heap, index):
    """Remove item from heap"""

    # Move slot to be removed to top of heap
    while index > 0:
        up = (index + 1) / 2 - 1
        heap[index] = heap[up]
        index = up

    # Remove top of heap and restore heap property
    heapq.heappop(heap)

Answer 4

Существует структура данных, называемая treap , которая представляет собой очередь с приоритетами и двоичное дерево вместе.(Дерево-куча).Он позволяет выполнять поиск по логину, который может вам помочь.

Существует реализация Python Treap на PyPi ..;)