Каковы наихудшие временные границы для каждой операции в куче Фибоначчи?
Кучи Фибоначчи эффективны в амортизированном смысле, но насколько они эффективны в худшем случае? В частности, какова временная сложность наихудшего случая каждой из этих операций в куче Фибоначчи с n-узлом?
- найти мин
- удалить-мин
- вставить
- снижение ключа
- сливаться
2 ответа
Операция find-min для кучи Фибоначчи всегда занимает наихудшее время O(1). Всегда поддерживается указатель, который напрямую указывает на этот объект.
Стоимость удаления мин в худшем случае занимает время Θ(n). Чтобы увидеть это, представьте, что вы начинаете с пустой кучи и выполняете серию n вставок в нее. Каждый узел будет храниться в своем собственном дереве, и, выполнив delete-min, куча объединит все эти объекты в O(log n) деревьев, что потребует Θ (n) работы, чтобы посетить все узлы хотя бы один раз.
Стоимость вставки в худшем случае O(1); это просто создание одного узла и добавление его в список. Слияние аналогично O(1), поскольку оно просто объединяет два списка.
Стоимость ключа уменьшения в худшем случае составляет Θ(n). Можно построить вырожденную кучу Фибоначчи, в которой все элементы хранятся в одном дереве, состоящем из связанного списка из n отмеченных узлов. Выполнение клавиши уменьшения на самом нижнем узле затем запускает серию каскадных срезов, которые преобразуют дерево в n независимых узлов.
Я почти согласен с отличным ответом от @templatetypedef.
Не может быть дерева классической кучи Фибоначчи с $n$ размеченными узлами. Это означало бы, что высота дерева равна O(n), но поскольку для каждого поддерева ранга $k$ его потомки имеют ранги $\geq 0, \geq 1, ..., \geq k-1$. Легко видеть, что глубина дерева не превосходит O(logn). И поэтому одна операция с нажатием клавиши Decrease может стоить O(logn).
Я проверил этот поток , и он требует некоторой модификации кучи Фибоначчи, так как он пометил узел в корневом списке и выполняет операции, которые не принадлежат куче Фибоначчи.