Как я могу реализовать функциональные возможности сокращения в Python heapq?

Ответ 1

Чтобы эффективно реализовать "уменьшающий ключ", вам нужно получить доступ к функциональности "уменьшить этот элемент и заменить этот элемент дочерним, пока не будет восстановлено состояние кучи". В heapq.py, который называется _siftdown (и аналогичным образом _siftup для INcrementing). Таким образом, хорошая новость заключается в том, что функции существуют... Плохая новость заключается в том, что их имена начинаются с подчеркивания, указывая, что они считаются "внутренними деталями реализации" и не должны быть доступны напрямую по коду приложения (следующий выпуск стандартная библиотека может изменить ситуацию и сломать код с помощью таких "внутренних" ).

Вам решать, следует ли игнорировать предупреждение, ведущее- _, использовать O (N) heapify вместо O (log N) sifting или переопределить некоторые или все функции heapq, чтобы сделать просеивающие примитивы ", выставленные как открытые части интерфейса". Поскольку структура данных heapq документирована и общедоступна (просто список), я думаю, что лучший выбор, вероятно, является частичным повторным выполнением - по существу, скопируйте функции отсеивания из heapq.py в ваш код приложения.

Ответ 2

документация heapq содержит запись о том, как это сделать.

Однако я написал пакет heap, который делает именно это (это обертка вокруг heapq). Поэтому, если у вас есть pip или easy_install, вы можете сделать что-то вроде

pip install heap

Затем в вашем коде напишите

from heap.heap import heap

h = heap()

h['hello'] = 4 # Insert item with priority 4.

h['hello'] = 2 # Update priority/decrease-key has same syntax as insert. 

Это довольно ново, так что может быть множество ошибок.

Ответ 3

Представьте, что вы используете кучу в качестве очереди приоритетов, где у вас есть множество задач, представленных строками, и каждая задача имеет ключ. Для конкретности посмотрите: task_list = [[7,"do laundry"], [3, "clean room"], [6, "call parents"]] где каждая задача в task_list - это список с приоритетом и описанием. Если вы запустите heapq.heapify(task_list), вы получите массив для сохранения инварианта кучи. Однако, если вы хотите изменить приоритет "сделать стирку" на 1, вы не можете узнать, где "сделать белье" находится в куче без линейного сканирования через кучу (следовательно, он не может делать drop_key в логарифмическом времени), Примечание decrease_key(heap, i, new_key) требует, чтобы вы указали индекс значения для изменения в куче.

Даже если вы сохраняете ссылку на каждую подсписку и на самом деле меняете ключ, вы все равно не сможете это сделать в журнале. Поскольку список - это просто ссылка на кучу изменчивых объектов, вы можете попытаться сделать что-то вроде запоминания первоначального порядка задачи: (в этом случае "сделать стирку" было 0-й задачей в вашем оригинале task_list):

task_list = [[7, "do laundry"], [3, "clean room"], [6, "call parents"]]
task_list_heap = task_list[:] # make a non-deep copy
heapq.heapify(task_list_heap)
# at this point:
# task_list = [[7, 'do laundry'], [3, 'clean room'], [6, 'call parents']]
# task_list_heap = [3, 'clean room'], [7, 'do laundry'], [6, 'call parents']]
# Change key of first item of task_list (which was "do laundry") from 7 to 1.
task_list[0][0] = 1
# Now:
# task_list = [[1, 'do laundry'], [3, 'clean room'], [6, 'call parents']]
# task_list_heap = [3, 'clean room'], [1, 'do laundry'], [6, 'call parents']]
# task_list_heap violates heap invariant at the moment

Однако теперь вам нужно вызвать heapq._siftdown(task_list_heap, 1) для поддержания инварианта кучи в лог-времени (heapq.heapify является линейным временем), но, к сожалению, мы не знаем индекса "сделать стирку" в task_list_heap (heap_index в этом случае 1).

Итак, нам нужно реализовать, что наша куча отслеживает heap_index каждого объекта; например, иметь list (для кучи) и dict сопоставление каждого объекта с его индексом в списке кучи/списка (который обновляется по мере того, как позиции кучи меняются местами, добавляя постоянный коэффициент для каждого свопа). Вы можете прочитать heapq.py и реализовать себя, поскольку процедура проста; однако другие уже реализуют этот вид HeapDict.

Ответ 4

Клавиша уменьшения - обязательная операция для многих алгоритмов (Dijkstra Algorithm, A *, OPTICS), мне интересно, почему встроенная очередь приоритетов Python не поддерживает ее.

К сожалению, я не смог загрузить пакет math4tots.

Но я смог найти эту реализацию Daniel Stutzbach. Работала отлично для меня с Python 3.5.