Очередь приоритетов - список пропусков против кучи Фибоначчи

Question

Я заинтересован в реализации очереди приоритетов, чтобы обеспечить эффективную реализацию Astar, которая также относительно проста (я имею в виду, очередь приоритетов проста).

Кажется, что, поскольку в Skip List есть простая операция O (1) extract-Min и операция вставки O (Log N), он может конкурировать с более трудной реализацией Кучи Фибоначчи, в которой O (log N) ) Extract-Min и O (1) вставка. Я предполагаю, что Skip-List был бы лучше для графа с разреженными узлами, тогда как куча Фибоначчи была бы лучше для среды с более плотно связанными узлами.

Это, вероятно, улучшило бы кучу Фибоначчи, но я прав, если предположил, что в большом смысле это будет похоже?

Answer 1

Смысл существования кучи Фибоначчи - операция уменьшения ключа O (1), позволяющая алгоритму Дейкстры работать за время O (| V | log | V | + | E |).На практике, однако, если бы мне потребовалась эффективная операция уменьшения клавиши, я бы использовал кучу сопряжения, поскольку куча Фибоначчи имеет ужасные константы.Если ваши ключи - маленькие целые числа, может быть даже лучше просто использовать ячейки.

Answer 2

Кучи Фибоначчи очень-очень-очень медленные, за исключением очень-очень-очень больших и плотных графов (порядка сотен миллионов ребер). Их также сложно реализовать правильно.

С другой стороны, списки пропусков являются очень хорошими структурами данных и относительно просты в реализации.

Однако мне интересно, почему вы не рассматриваете возможность использования простой двоичной кучи. Я считаю, что очереди приоритетов на основе двоичной кучи даже быстрее, чем пропустить очереди на основе списка. Пропуск списков в основном используется для одновременного использования.