Реальные приложения двоичных куч и куч Фибоначчи [закрыто]
Используйте это.
$(function(){
$('input').keydown(function(e){
if (e.keyCode == 13) {
$("input[value='OK']").focus().click();
return false;
}
});
});
3 ответа
Вы бы редко использовали его в реальной жизни. Я полагаю, что цель кучи Фибоначчи состояла в том, чтобы улучшить асимптотическое время выполнения алгоритма Дейкстры. Это может дать вам улучшение для очень и очень больших входных данных, но в большинстве случаев вам нужна простая двоичная куча.
Из Вики:
Хотя общее время выполнения последовательности операций, начинающихся с пустой структуры, ограничено пределами, указанными выше, некоторые (очень немногие) операции в последовательности могут занять очень много времени. долго для завершения (в частности, удаление и удаление минимума имеют линейное время выполнения в худшем случае). По этой причине кучи Фибоначчи и другие амортизированные структуры данных могут не подходить для систем реального времени.
Бинарная куча - это структура данных, которую можно использовать для быстрого поиска максимального (или минимального) значения в наборе значений. Он используется в алгоритме Дейкстры (кратчайший путь), алгоритме Прима (минимальное связующее дерево) и кодировании Хаффмана (сжатие данных).
Не могу сказать о кучах Фибоначчи, но двоичные кучи используются в приоритетных очередях. Приоритетные очереди широко используются в реальных системах.
Одним известным примером является планирование процессов в ядре. Процесс с наивысшим приоритетом берется первым.
Я использовал очереди приоритетов при разбиении наборов . Набор с максимальным количеством членов должен был быть взят первым для разбиения.
В большинстве сценариев вы должны выбирать в зависимости от сложности:
- вставка
- поиск элементов
И обычные подозреваемые:
- BST:
log(n)вставить и найти - связанный список:
O(1)вставить иO(n)найти - куча:
-
O(1)вставьте- среднее значение для двоичной кучи, см .: https://stackoverflow.com/a/29548834/895245 )
- амортизировано для Фибоначчи. Это сильнее, чем в среднем, слабее, чем в худшем случае.
-
O(1)найдите только для первого элемента ,O(n)в общем- < li> худший случай для двоичной кучи
- амортизируется для Фибоначчи
Существует также очередь Brodal и другие кучи, которые достигают
O(1)наихудшего случая, но требуют еще больших очередей , чем Фибоначчи, чтобы того стоило.Так что, если вашему алгоритму нужно только «найти» первый элемент и выполнить много вставок, кучи - хороший выбор.
Как уже упоминалось, это относится и к Дейкстре.
-