Приоритетная очередь с функцией поиска - самая быстрая реализация

Ответ 1

Почему вы не можете использовать очередь приоритетов и набор? Когда вы вставляете что-то, вы добавляете его в набор. Когда вы удаляете его, вы удаляете его из набора. Таким образом, набор скажет вам, что-то находится в очереди.

Ответ 2

Если ваша операция поиска относительно нечастая (и ваша куча довольно маленькая), я бы просто выполнил линейный поиск. Если это относительно часто, или куча огромна, подумайте о том, чтобы отслеживать членство в куче (чтобы выполнить свой тест "найти" ) с отдельной структурой данных или флагом объекта. Радость внешнего индексирования позволяет разместить ваш объект в таком количестве контейнеров, сколько захотите.

Если "find" вы действительно имеете в виду "найти и изменить" (я считаю, что мне часто нужно удалять вещи из очередей приоритетов независимо от типичной вставки /del -min), вот три подхода, которые я использовал:

Учитывая высокую скорость вставки /del -min (непрерывность 100 к/с) и низкую скорость поиска-удаления (скажем, 1/с) на довольно небольшом рабочем наборе (500-1000), я сделал линейный поиск для и затем удалил его из дерева стандартным образом.

Учитывая высокую скорость ввода /del -min плюс довольно частые находки-удаления, я просто пометил удаленные объекты как "неинтересные" после их обнаружения косвенно. Фактический бесплатный был отложен до тех пор, пока объект не был отложен как обычно.

Учитывая небольшой std:: priority_queue (который не имеет методов доступа вне вставки /del -min) только нескольких элементов и довольно редких исключений, я просто скопировал всю очередь во временный std::vector и скопировал измененный/желаемая часть обратно в очередь. Затем я закричал, чтобы спать.

Ответ 3

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

Если он insert, тогда вставьте элемент в оба из них.

Если он find, то вы можете найти элемент, используя дерево двоичного поиска, и если он был найден, продолжайте поиск в очереди приоритетов.

Если он min, то сначала удалите его из очереди приоритетов, и теперь, когда вы знаете, какой элемент он есть, вы можете удалить его из двоичного дерева поиска.

если он del, то сначала найдите его в дереве двоичного поиска и удалите его, затем продолжите поиск в очереди приоритетов и удалите его тоже.

Предполагается, что узлы двоичного дерева и узлы очереди приоритетов являются указателями на ваши элементы.

Ответ 4

Поиск/поиск IIRC в куче O(n), тогда как на дереве это O(log(n)), а остальные стандартные операции PQ одинаковы.

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

Ответ 5

Деревья Radix с свойством min-heap предоставят нужные вам свойства. Это фактически даст вам постоянные временные сложности для ваших операций. Например, если мы рассмотрим эту реализацию Haskell, все три упомянутые вами операции имеют временную сложность O (min (n, W)). Где n - количество элементов, а W - количество бит в int (32 или 64).

Ответ 6

Храните данные в самом быстром контейнере, который вы протестировали, и используйте фильтр цветка, чтобы проверить, что-то находится в контейнере.

Я связал фильтр цветка с хеш-таблицей в предыдущем проекте, и он ускорил работу до 400 раз по хэш-таблицам со средним количеством примерно 10 тыс. элементов.

Фильтр цветения имеет несколько интересных свойств:

• Если ответ отсутствует от фильтра цветения, он на 100% надежный.
• Если да, вы должны проверить другие данные чтобы убедиться, что элемент действительно присутствует.
• Убедитесь, что вы выбрали хорошую хэш-функцию:)