403
правки
Изменения
→Операции
== Операции ==
Рассмотрим операции, которые поддерживают фибоначчиевы кучи. Амортизированное время их работы показано в таблице.
{| border="1"
|-align="center"
|<tex>makeHeap</tex>
|<tex>\Theta(1)</tex>
|-align="center"
|<tex>insert</tex>
|<tex>\Theta(1)</tex>
|-align="center"
|<tex>getMin</tex>
|<tex>\Theta(1)</tex>
|-align="center"
|<tex>extractMin</tex>
|<tex>O(\log(n))</tex>
|-align="center"
|<tex>merge</tex>
|<tex>\Theta(1)</tex>
|-align="center"
|<tex>decreaseKey</tex>
|<tex>\Theta(1)</tex>
|-align="center"
|<tex>delete</tex>
|<tex>O(\log(n))</tex>
|}
Стоит заметить, что структура фибоначчиевых куч, также как биномиальных и бинарных, не могут обеспечить эффективную реализацию поиска элемента с заданным ключом, поэтому операции <tex>decreaseKey</tex> и <tex>delete</tex> получают в качестве аргумента указатель на узел, а не значение его ключа.
== Потенциал ==
