Сливаемая куча () — структура данных, которая поддерживает следующие пять операций: Создание пустой кучи (); Вставка узла в кучу (); Поиск узла в куче , который обладает минимальным ключом (); Удаление узла с минимальным ключом из кучи (); Создание новой кучи , которая содержит все узлы куч и ().
Реализации Следующие две структуры данных являются реализациями сливаемой кучи: Биномиальная куча; Фибоначчиева куча.
Эти структуры данных так же поддерживают еще 2 операции: Присваивание узлу в куче нового значения ключа () (предполагается, что новое значение ключа не превосходит текущего); Удаление узла из кучи ().
+ Время выполнения операций у разных реализаций сливаемых пирамид Операция Биномиальная куча Фибоначчиева куча Make heap Θ(1) Θ(1) Insert O(lgn) Θ(1) Minimum O(lgn) Θ(1) Extract minimum Θ(lgn) O(lgn) Union Ω(lgn) Θ(1) Decrease key Θ(lgn) Θ(1) Delete Θ(lgn) O(lgn)
Примечание: для Биномиальной кучи время в наихудшем случае, для Фибоначчиевой кучи амортизированное время.
Замечание. По умолчанию сливаемые кучи являются неубывающими сливаемыми кучами (). Также существуют невозрастающие сливаемые кучи (), которые поддерживают следующие операции: Создание пустой кучи (); Вставка узла в кучу (); Поиск узла в куче , который обладает максимальныи ключом (); Удаление узла с максимальныи ключом из кучи (); Создание новой кучи , которая содержит все узлы куч и (). Присваивание узлу в куче нового значения ключа (); Удаление узла из кучи ().
Литература
Категория:Структуры данных Категория:Кучи (структуры данных)