Приоритетная очередь — список пропуска против кучи Фибоначчи

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

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

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


algorithm heap priority-queue skip-lists fibonacci-heap
person user_48349383    schedule 27.07.2011    source источник
comment
Что не так с обычной бинарной мин-кучей?   -  person Thomas Jungblut    schedule 27.07.2011

Ответы (2)


arrow_upward
6
arrow_downward

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

person cutting plane    schedule 27.07.2011
comment
(Если вам нужна простая и достаточно эффективная библиотека, трудно сделать лучше, чем стандартная библиотека.) - person cutting plane; 27.07.2011
comment
Куча Фибоначчи в любом случае трудно реализуема и в основном представляет теоретический интерес. Операция объединения выполняется за O(1), что является еще одной причиной, по которой может возникнуть желание изучить эту структуру данных. - person OckhamsRazor; 23.04.2012

arrow_upward
4
arrow_downward

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

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

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

person tskuzzy    schedule 27.07.2011
comment
Одна только двоичная куча не будет работать, потому что требуется O(n), чтобы найти конкретный узел и обновить его приоритет (в данном случае агрегированное расстояние от источника). Однако вы можете ввести дополнительную unordered_map для O (1) местоположения узла, тогда это уменьшит сложность до O (logn), что определяется узким местом heapify после обновления вашего приоритета. - person h9uest; 06.04.2015