SplMinHeap и lowerKey - PullRequest
Новая
       28

SplMinHeap и lowerKey

0 голосов
/ 08 июня 2011

короткий вопрос:

Есть ли способ реализовать эффективный метод lowerKey для SplMinHeap (или любой из куч Spl) без потерибонус за производительность?

Справочная информация:

Для частного проекта я играю с реализацией класса A * и надеюсь получить повышение производительности, используяодна из структур кучи spl.Но я не могу понять, как их использовать, поскольку у них нет методов decreaseKey или contains.Может быть, я что-то упустил полностью?

Большое спасибо!

1 Ответ

0 голосов
/ 08 июня 2011

Чтобы реализовать метод decreaseKey, нам нужно:

  1. Найти запись в куче и уменьшить ее ключ на единицу.
  2. Выполнять восходящее всплытие до тех пор, покаСвойство heap-order полностью восстановлено.

Если нам не нужна запись с наименьшим ключом, мы вообще не знаем, где хранятся записи.Более того, даже если мы найдем запрошенную запись в приемлемое время, мы просто не сможем обновить ее ключ в отношении методов SplMinHeap.

Так что я не вижу эффективного способа реализации decreaseKeyметод со структурой данных SplMinHeap.Возможно, вам следует реализовать YourHeap с YourCompleteBinaryTree, реализованным, например, с помощью YourArrayList.

...