Реальные приложения для двоичных куч и кучи Фибоначчи

Ответ 1

Вы редко использовали бы это в реальной жизни. Я считаю, что цель кучи Фибоначчи заключалась в том, чтобы улучшить асимптотическое время работы алгоритма Дейкстры. Это может дать вам улучшения для очень и очень больших входов, но большую часть времени вам нужна простая двоичная куча.

Из Wiki:

Хотя общее время работы последовательность операций, начиная с пустая структура ограничена приведенные выше, некоторые (очень немногие) операции в последовательности могут очень долго заканчивается (в частности удалить и удалить минимум имеют линейные время работы в худшем случае). Для по этой причине кучи Фибоначчи и другие амортизированные структуры данных могут не быть подходит для систем реального времени.

Двоичная куча - это структура данных, которая может использоваться для быстрого нахождения максимального (или минимального) значения в наборе значений. Он используется в алгоритме Дейкстры (кратчайший путь), алгоритме Прима (минимальное остовное дерево) и кодировании Хаффмана (сжатие данных).

Ответ 2

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

Ответ 3

Приоритетные очереди обычно выполняются как кучи, например: http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html

Вычисление верхних N элементов из огромного набора данных может быть эффективно осуществлено с использованием двоичных куч (например, верхние поисковые запросы на крупномасштабном веб-сайте).

Ответ 4

В большинстве сценариев вы должны выбрать на основе сложности:

• вставки
• поиск элементов

И обычные подозреваемые:

• BST: log(n) вставить и найти
• связанный список: O(1) вставить и O(n) найти
• куча:
  • O(1) вставить
    • среднее значение для двоичной кучи, см. fooobar.com/info/57217/...)
    • амортизируется для Фибоначчи. Это сильнее, чем средний, более слабый, чем худший.
  • O(1) найти только для первого элемента, O(n) в целом
    • худший случай для двоичной кучи
    • амортизировано для Фибоначчи

Существует также очередь Brodal и другие кучи, которые достигают наихудшего случая O(1), но требуют еще большие очереди, чем Фибоначчи, чтобы быть достойными.

Итак, если вашему алгоритму нужно только "найти" первый элемент и сделать много вложений, кучи - хороший выбор.

Как упоминалось, это относится и к Дейкстре.