Куча, которая поддерживает модификацию своих элементов?

Question

Вот мой сценарий. Я хочу реализовать A * (в Python) без необходимости прибегать к минимальному линейному времени или операциям. Мне нужна куча, чтобы иметь возможность эффективно получить предмет с наименьшим весом.

Мой немедленный ответ был «Легко! Я буду использовать heapq! Затем я обнаружил, что жизнь редко бывает такой простой, какой нам хотелось бы. Оказывается, эта стратегия является неоптимальной для одной из критических точек A *. Когда речь идет о детях, мне нужно периодически обновлять оценки детей, уже находящихся в куче.

Для тех, чья память об A * немного устарела, суть в том, что я хочу взять элемент, изменить его вес и изменить кучу, чтобы отразить изменение, все в сублинейном времени.

Есть предложения?

Answer 1

В целях сложности вы можете попробовать биномиальную кучу или кучу Фибоначчи;похоже, что в Python есть реализации обоих, но нет библиотек промышленного уровня.Однако двоичная или d-ary куча может работать быстрее на практике.На странице heapq упоминается, как выполнять обновления (сохраните ссылку на элемент, который вы вставляете в кучу, отметьте его как недействительный, а затем вставьте новую версию).Однако существуют более быстрые алгоритмы для поддержания свойства кучи после обновлений.Посмотрите на http://en.wikipedia.org/wiki/D-ary_heap алгоритмы, используемые для быстрых обновлений, но вам, вероятно, потребуется реализовать собственную кучу поверх массива для них.

Answer 2

Я всегда заканчиваю тем, что реализовал свою собственную версию типа Heap по той самой причине, что вы не можете на самом деле искать в Heap, в то время как все эффективные методы требуют «указатель на элемент» в качестве входных данных.

Обычно я реализую свою кучу как комбинацию неструктурированного контейнера Предметов и кучи указателей (или индексов) на Предметы. Если вы сохраняете указатель на расположение кучи в элементе, у вас есть прямая двусторонняя ссылка: a) Дан элемент Heap (например, возвращенный extractMin или во время сравнения): разыменуйте указатель, и вы получите свой элемент. b) Для данного элемента (например, через список смежности алгоритма Graph): передайте указатель на любую функцию обновления, которую вы хотите.

Конечно, это приводит к накладным расходам пространства (2 дополнительных указателя / целых числа на элемент), но это делает реструктуризацию кучи очень дешевой (замена нескольких указателей вместо замены целых элементов), что, в свою очередь, делает менее болезненным добавление некоторых дополнительных спутниковые данные для ваших предметов.

Answer 3

Это правда, ни функции кучи в heapq, ни Queue.PriorityQueue не очень функциональны.Вероятно, это займет примерно столько же времени, что и для A: напишите в своем блоге напыщенную речь, или для B: внедрите ее самостоятельно.