Где-нибудь на практике используются кучи Фибоначчи или очереди Бродала?

Question

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

1. Есть хорошие реализации куч Фибоначчи, в том числе в стандартных библиотеках, таких как Boost C++. Тот факт, что эти библиотеки содержат кучи Фибоначчи, предполагает, что они должны быть где-то полезны.
2. Мы знаем, что для того, чтобы куча Фибоначчи была быстрее на практике, должны быть соблюдены определенные условия: " чтобы использовать кучи Фибоначчи на практике, вы должны использовать их в приложении, в котором невероятно часто встречаются сокращения_ключей"; " Чтобы куча Фибоначчи действительно сияла, вам понадобится один из следующих случаев: а) дорогие сравнения: кучи Фибоначчи сводят к минимуму количество сравнений, необходимых для организации данных. Б) Большинство операций - updateKey / insert / delete. Как и Фибоначчи Объединяет обновления в группы до следующего extractMin: чем больше "пакет", тем эффективнее он становится".
3. Существует структура данных, называемая "Бродал-очередь", о которой я не уверена, что слышала раньше, которая, кажется, имеет поведение сложности времени, по крайней мере, такое же хорошее, как кучи Фибоначчи. Вот хорошая таблица со сравнением временных сложностей для разных операций для разных разновидностей куч.
4. На вопрос о том, существуют ли какие-либо применения Фибоначчи или биномиальных куч, ответчики привели только примеры биномиальных куч.

Answer 1

Насколько я знаю, нет никаких главных приложений, которые фактически используют кучи Фибоначчи или очереди Бродала.

Кучи Фибоначчи были изначально разработаны для удовлетворения теоретической, а не практической необходимости: асимптотически ускорить алгоритм Дейкстры по кратчайшим путям. Очередь Бродала (и связанная функциональная структура данных) были аналогичным образом разработаны для удовлетворения теоретических гарантий, в частности, для ответа на давний открытый вопрос о том, можно ли сопоставить временные границы кучи Фибоначчи с гарантиями наихудшего случая, а не с амортизированными гарантиями, В этом смысле структуры данных были разработаны не для удовлетворения практических потребностей, а скорее для продвижения нашего теоретического понимания пределов алгоритмической эффективности. Насколько мне известно, в настоящее время не существует алгоритмов, в которых было бы лучше использовать очередь Бродала над кучей Фибоначчи.

Как отмечали другие ответы, постоянные факторы, скрытые в куче Фибоначчи или очереди Бродала, очень высоки. Им нужно много указателей, соединенных во множество сложных связанных списков, и, соответственно, они имеют абсолютно ужасную привязку, особенно по сравнению со стандартной двоичной кучей. Это означает, что они, вероятно, будут хуже работать на практике с учетом эффектов кэширования, если у вас нет алгоритмов, которые требуют колоссально большого количества операций с уменьшением ключа. В некоторых случаях это происходит (например, в связанных ответах говорится о некоторых из них), но они рассматриваются как узкоспециализированные обстоятельства, а не как случаи общего использования. Если вы работаете с огромными графиками, для повышения эффективности чаще используются другие методы, такие как алгоритмы аппроксимации для рассматриваемой задачи, улучшенная эвристика или алгоритмы, использующие конкретные свойства базовых данных.

Надеюсь это поможет!

Answer 2

Кучи Фибоначчи используются в Velvet, короткометражном ассемблере по биоинформатике.

См. раздел «Проблемы сложности и масштабирования» статьи: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2336801/ .

Выдержка, выделение мое:

Основным узким местом с точки зрения времени и памяти является построение графа. Первоначальный график чтения стрептококка требует 2,0 ГБ оперативной памяти. Масштаб проблемы в конечном итоге потребует создания постоянных в памяти структур данных для сборок всего генома. Конечно, время доступа будет больше, но объем сохраняемых данных будет практически неограниченным. Временная сложность Tour Bus зависит в первую очередь от количества N узлов в графе, которое в свою очередь зависит от покрытия чтения, частоты ошибок и количества повторов. Идури и Уотерман (1995) оценили N, но не учли повторения. Сам поиск основан на алгоритме Дейкстры, временная сложность которого составляет O(N logN) при реализации с кучей Фибоначчи (Gross and Yellen 2004). Стоимость сравнения отдельных путей и соответствующих модификаций графа может быть ограничена ограничением длины.