Скачать или смотреть Создание и вставка кучи Фибоначчи

#techlearners
Кучи Фибоначчи — это связанные списки упорядоченных куч.
Деревья со следующими характеристиками:
Деревья не обязательно биномиальны.
Семьи связаны двунаправленно.
Существует указатель min{H] на корень с минимальным ключом.
Степени корней не уникальны.
Специальные атрибуты n[H] поддерживают общее количество узлов.
Узлы могут быть помечены.

Создание кучи Фибоначчи
Для создания пустой кучи Фибоначчи процедура MAKE_FIB_HEAP выделяет и возвращает объект кучи Фибоначчи H, где n[H]=0 и min[H]=Nil.

Амортизированная стоимость MAKE_FIB_HEAP составляет O(1).

Вставка кучи Фибоначчи
Создание нового одноэлементного дерева.
Добавление слева от указателя min.
Обновление указателя min.

Время выполнения. Амортизированная стоимость O(1).
Фактическая стоимость = O(1).
Изменение потенциала = +1.
Амортизированная стоимость = O(1).

TECHLEARNERS, автор: Нирадж Саксена
http://www.techlearners.co.in