Изменения

Перейти к: навигация, поиск

Фибоначчиева куча

321 байт добавлено, 18:58, 21 мая 2015
Структура списка детей
====Структура списка детей====
[[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]
* Дочерние узлы <tex>x</tex> объединены при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический ]] [[Список#Двусвязный список | двусвязный список]].* Корни всех деревьев в <tex>H</tex> связаны при помощи указателей <tex>left</tex> и <tex>right</tex> в [[Список#Циклический список |циклический ]] [[Список#Двусвязный список | двусвязный список ]] корней.
[[Список#Циклический список |Циклический]] [[Список#Двусвязный список | двусвязный список ]] обладает двумя преимуществами для использования в фибоначчиевых кучах. Во-первых, удаление элемента из такого списка выполняется за время <tex>O(1)</tex>. Во-вторых, если имеется два таких списка, их легко объединить в один за время <tex>O(1)</tex>.
=== Потенциал ===
Анонимный участник

Навигация