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

Question

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

Изменить: Добавлены двоичные кучи также. Любопытно узнать.

Answer 1

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

Из вики:

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

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

Answer 2

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

Одним известным примером является планирование процессов в ядре. Процесс с наивысшим приоритетом берется первым.

Я использовал очереди приоритетов при разбиении наборов. Набор с максимальным количеством членов должен был быть взят первым для разбиения.

Answer 3

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

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

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

• BST: log(n) вставить и найти
• связанный список: O(1) вставить и O(n) находить
• куча:
  • O(1) вставить
    • среднее значение для двоичной кучи, см.: /questions/13541891/kucha-protiv-binarnogo-dereva-poiska-bst/13541892#13541892)
    • амортизируется по Фибоначчи. Это сильнее, чем в среднем, слабее, чем в худшем случае.
  • O(1) найти только для первого элемента, O(n) в общем
    • худший случай для двоичной кучи
    • амортизируется по Фибоначчи

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

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

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

Answer 4

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

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