Изменения
Нет описания правки
=== Операции ===
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.
{| borderstyle="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| Операция!style="1background-color:#EEE"| Амортизированная сложность |-align="center" |style="background-color:#FFF;padding:2px 10px"|<tex>\mathrm {makeHeap}</tex> |style="background-color:#FFF;padding:2px 10px"|<tex>O(1)</tex> |-align="center" |style="background-color:#FFF;padding:2px 10px"|<tex>\mathrm {insert}</tex> |style="background-color:#FFF;padding:2px 10px"|<tex>O(1)</tex> |-align="center" |style="background-color:#FFF;padding:2px 10px"|<tex>\mathrm {getMin}</tex> |style="background-color:#FFF;padding:2px 10px"|<tex>O(1)</tex> |-align="center" |style="background-color:#FFF;padding:2px 10px"|<tex>\mathrm {merge}</tex> |style="background-color:#FFF;padding:2px 10px"|<tex>O(1)</tex> |-align="center" |style="background-color:#FFF;padding:2px 10px"|<tex>\mathrm {extractMin}</tex> |style="background-color:#FFF;padding:2px 10px"|<tex>O(\log n )</tex> |-align="center" |style="background-color:#FFF;padding:2px 10px"|<tex>\mathrm {decreaseKey}</tex> |style="background-color:#FFF;padding:2px 10px"|<tex>O(1)</tex> |-align="center" |style="background-color:#FFF;padding:2px 10px"|<tex>\mathrm {delete}</tex> |style="background-color:#FFF;padding:2px 10px"|<tex>O(\log n )</tex> |}
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>\mathrm {decreaseKey}</tex> и <tex>\mathrm {delete}</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.
